計算DNA序列

Question

你能告訴我怎樣可以通過Java中使用Levenshtein算法

Answer 1

的wiki的萊文斯坦包含算法和結果矩陣的解釋計算的DNA序列。只需將算法實現爲一個方法並返回矩陣中的最後一個元素。

Answer 2

這裏是the Wikipedia page on Levenshtein distances算法：

int LevenshteinDistance(char s[1..m], char t[1..n]) 
{ 
    // d is a table with m+1 rows and n+1 columns 
    declare int d[0..m, 0..n] 

    for i from 0 to m 
    d[i, 0] := i // deletion 
    for j from 0 to n 
    d[0, j] := j // insertion 

    for j from 1 to n 
    { 
    for i from 1 to m 
    { 
     if s[i] = t[j] then 
     d[i, j] := d[i-1, j-1] 
     else 
     d[i, j] := minimum 
        (
         d[i-1, j] + 1, // deletion 
         d[i, j-1] + 1, // insertion 
         d[i-1, j-1] + 1 // substitution 
        ) 
    } 
    } 

    return d[m, n] 
} 

（我敢肯定，你可以讓Java出來，隨着一點點的工作。）

通在你的兩個DNA序列s和t它會返回一個int的距離。從Levenshtein Distance Algorithm

Answer 3

複製/粘貼功能，並使用它像這樣：

String a = "AAAAAAAAAAAAAAAAAA"; 
String b = "AAAAAAAAACTAAAAAAA"; 

int d = getLevenshteinDistance(a,b); 
System.out.println(d); 

Answer 4

如果您是計算兩個DNA序列之間的差異只是有興趣，你應該使用Damerau–Levenshtein distance不是正規的Levenshtein距離。

維基百科條目包含一些示例代碼，您當然可以映射到java代碼。

Answer 5

我相信這是你所追求的。如果您願意，您可以刪除System.out.println聲明。請注意，如果將它們留在中，則第一行和第一列在打印的內容中被省略。

對照results on the wikipedia page進行驗證。

public int getLevenshteinDistance(String a, String b) 
{ 
    // d is a table with m+1 rows and n+1 columns 
    char[] s = (a).toCharArray(); 
    char[] t = (b).toCharArray(); 
    System.out.println(a + " - " + b); 
    int m = s.length; 
    int n = t.length; 
    int[][] d = new int[m + 1][n + 1]; 

    int i; 
    int j; 
    for(i = 0; i < (m + 1); i++) 
    { 
     d[i][0] = i; //deletion 
    } 

    for(j = 0; j < (n + 1); j++) 
    { 
     d[0][j] = j; //insertion 
    } 

    for (j = 1; j < (n + 1); j++) 
    { 
     for (i = 1; i < (m + 1); i++) 
     { 
      if (s[i-1] == t[j-1]) 
      { 
       d[i][j] = d[i-1][j-1]; 
      } 
      else 
      { 
       d[i][j] = Math.min((d[i-1][j] + 1), //deletion 
         (Math.min((d[i][j-1] + 1), //insertion 
         (d[i-1][j-1] + 1)))); //substitution 
      } 
      System.out.print(" [" + d[i][j] + "]"); 
     } 
     System.out.println(""); 
    } 

    return d[m][n]; 
} 

測試：

String a = "Saturday"; 
    String b = "Sunday"; 
    int d = getLevenshteinDistance(a, b); 
    System.out.println(d); 
    a = "kitten"; 
    b = "sitting"; 
    d = getLevenshteinDistance(a, b); 
    System.out.println(d); 

Answer 6

既然你沒有把它標記作爲功課，我看到寫這你自己沒有必要。 Apache's StringUtils has it。