Need help implementing a dynamic DNA comparison algorithm in java. The program n

Question

Need help implementing a dynamic DNA comparison algorithm in java. The program needs to read two strings (one string per line) from a local text file, compute, and report the edit distance between the string sequences which consist of characters {A,T,C, or G}. The edit distance is defined as the minimum number of operations (insertion, deletion, and replacement) required to transform one string into the other.

Example: When given Given two sequences; a = a1, .... ,am and b = b1, ... bn

http://pastebin.com/q8Wt8H5N

Explanation / Answer

public static int minDistance(String word1, String word2) {
   int len1 = word1.length();
   int len2 = word2.length();

   // len1+1, len2+1, because finally return dp[len1][len2]
   int[][] dp = new int[len1 + 1][len2 + 1];

   for (int i = 0; i <= len1; i++) {
       dp[i][0] = i;
   }

   for (int j = 0; j <= len2; j++) {
       dp[0][j] = j;
   }

   //iterate though, and check last char
   for (int i = 0; i < len1; i++) {
       char c1 = word1.charAt(i);
       for (int j = 0; j < len2; j++) {
           char c2 = word2.charAt(j);

           //if last two chars equal
           if (c1 == c2) {
               //update dp value for +1 length
               dp[i + 1][j + 1] = dp[i][j];
           } else {
               int replace = dp[i][j] + 1;
               int insert = dp[i][j + 1] + 1;
               int delete = dp[i + 1][j] + 1;

               int min = replace > insert ? insert : replace;
               min = delete > min ? min : delete;
               dp[i + 1][j + 1] = min;
           }
       }
   }

   return dp[len1][len2];
}

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.