0

你能告诉我如何使用 Levenshtein 算法通过 Java 计算 DNA 序列吗

4

6 回答 6

3

由于您没有将其标记为作业，因此我认为没有必要自己编写。Apache 的 StringUtils 有它。

于 2009-11-16T07:38:21.577 回答
2

这是来自Wikipedia 页面上 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 序列作为sand传递，t它将以 int 形式返回距离。

于 2009-11-16T05:26:50.110 回答
2

我相信这就是你所追求的。如果您愿意，可以删除这些System.out.println语句。请注意，如果您将它们留在其中，则打印的内容中会省略第一行和第一列。

根据维基百科页面上的结果进行了验证。

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);
于 2009-11-16T07:21:44.683 回答
0

Levenshtein的wiki包含算法和结果矩阵的解释。只需将算法实现为方法并返回矩阵中的最后一个元素。

于 2009-11-16T05:26:34.860 回答
0

从Levenshtein Distance Algorithm复制/粘贴函数并像这样使用它：

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

 int d = getLevenshteinDistance(a,b);
 System.out.println(d);
于 2009-11-16T05:29:59.323 回答
0

如果您只是对计算两个 DNA 序列之间的变异感兴趣，您应该使用Damerau-Levenshtein 距离，而不是常规的 Levenshtein 距离。

维基百科条目包含一些示例代码，您肯定能够将其映射到 java 代码。

于 2009-11-16T05:31:43.797 回答