Расчет последовательности ДНК

Question

Не могли бы вы сказать, как я могу рассчитать последовательности ДНК с помощью Java с использованием алгоритма Левенштейна

Answer 1

Так как вы не отметили это как домашнее задание, я не вижу необходимости писать это самостоятельно. У Apache StringUtils есть .

Answer 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);

Answer 3

Вот алгоритм из страницы Википедии о расстояниях Левенштейна :

 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 с небольшой работой.)

передайте ваши две последовательности ДНК как s и t, и расстояние будет возвращено как int.

Answer 4

Если вы просто заинтересованы в расчете вариации между двумя последовательностями ДНК, вам следует использовать расстояние Дамерау – Левенштейна , а не обычное расстояние Левенштейна.

Запись в Википедии содержит пример кода, который вы наверняка сможете сопоставить с кодом Java.

Answer 5

Скопируйте / вставьте функцию из алгоритма расстояния Левенштейна и используйте его так:

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

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

Answer 6

wiki для Левенштейна содержит алгоритм и объяснение полученной матрицы. Просто реализуйте алгоритм как метод и верните последний элемент в матрице.