DNA序列的计算

Question

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

Answer 1

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

Answer 2

以下是关于编辑距离的维基百科页面的算法：（

 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]
 }

我相信你可以）

将你的两个 DNA 序列作为 s 和 t 传递，它将以 int 形式返回距离。

Answer 3

我相信这就是你所追求的。如果您愿意，可以删除 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);

Answer 4

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

Answer 5

复制/粘贴 Levenshtein Distance Algorithm 中的函数并像使用它一样所以：

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

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

Answer 6

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

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