0

レーベンシュタインアルゴリズムを使用してJavaでDNA配列を計算する方法を教えてください

4

6 に答える 6

3

宿題のタグを付けていないので、自分で書く必要はないと思います。ApacheのStringUtilsにはそれがあります。

于 2009-11-16T07:38:21.577 に答える
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 に答える
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]
 }

(少しの作業で Java を作成できると確信しています。)

2 つの DNA シーケンスをsandとして渡すtと、距離が int として返されます。

于 2009-11-16T05:26:50.110 に答える
0

Levenshteinのwikiには、アルゴリズムと結果の行列の説明が含まれています。アルゴリズムをメソッドとして実装し、行列の最後の要素を返すだけです。

于 2009-11-16T05:26:34.860 に答える
0

レーベンシュタイン距離アルゴリズムから関数をコピーして貼り付け、次のように使用します。

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

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

2 つの DNA 配列間の差異を計算することにのみ関心がある場合は、通常のレーベンシュタイン距離ではなく、ダメラウ-レーベンシュタイン距離を使用する必要があります。

ウィキペディアのエントリには、Java コードに確実にマッピングできるサンプル コードが含まれています。

于 2009-11-16T05:31:43.797 に答える