Calcul de séquences d'ADN

Question

Pourriez-vous me dire comment je peux calculer les séquences d'ADN en Java en utilisant l'algorithme de Levenshtein

Answer 1

Le wiki pour Levenshtein contient un algorithme et une explication de la matrice résultante. Implémentez simplement l'algorithme comme méthode et renvoyez le dernier élément de la matrice.

Answer 2

Voici l'algorithme de 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] 
} 

(je suis sûr que vous pouvez faire java de cela avec un peu de travail.)

passe dans vos deux séquences d'ADN comme s et t et il retournera la distance comme int.

Answer 3

Copier/Coller la fonction de la Levenshtein Distance Algorithm et l'utiliser comme ceci:

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

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

Answer 4

Si vous êtes simplement intéressé à calculer la variation entre les deux séquences d'ADN, vous devez utiliser le Damerau–Levenshtein distance pas la distance Levenshtein régulière.

L'entrée wikipedia contient un exemple de code que vous êtes sûrement capable de mapper en code java.

Answer 5

Je crois que c'est ce que vous recherchez. Vous pouvez supprimer les instructions System.out.println si vous le souhaitez. Notez que si vous les laissez dans, la première ligne et les colonnes sont omises de ce qui est imprimé.

Vérifié contre le 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]; 
} 

Pour tester:

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

Comme vous ne l'avez pas taguer comme devoirs, je ne vois pas besoin par écrit vous-même. Apache's StringUtils has it.