/**
* Skeleton code for Edit Distance Computation of DNA sequences.
* The DNA sequence consists of four characters only: {A, C, G, T}.
* You are required to implement the minDistance method by dynamic programming.
* The edit costs are defined in EditCost class.
*
* The given code is provided to assist you to complete the required tasks. But the
* given code is often incomplete. You have to read and understand the given code
* carefully, before you can apply the code properly. You might need to implement
* additional procedures, such as error checking and handling, in order to apply the
*/
package Midterm.Q3;
public class EditDistance {
/* Compute the minimal total cost of character edits between two DNA sequences by dynamic programming.
*
* @param seq1 the original sequence.
* @param seq2 the target sequence.
* @return the minimal cost of the character edits.
*/
public static int minDistance(String seq1, String seq2){
// TODO: Complete this method
// START YOUR CODE
int lenseq1 = seq1.length();// seq1-source
int lenseq2 = seq2.length();// seq2-target
int[][] dp = new int[lenseq1+1][lenseq2+1];
dp[0][0] = 0;
for(int i=0;i<=lenseq1;i++){
dp[i][0] =i;
}
for(int j=0;j<=lenseq2;j++){
dp[0][j] = j;
}
for(int i = 1; i <= lenseq1; i++){
for(int j = 1; j<= lenseq2; j++){
if(seq1.charAt(i-1) == seq2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1];
}
else{
int insert = dp[i][j-1] +EditCost.getInsertCost(EditCost.convertToIndex(seq2.charAt(j-1)));
int delete = dp[i-1][j] + EditCost.getDeleteCost(EditCost.convertToIndex(seq1.charAt(i-1))) ;
int replace = dp[i-1][j-1] +EditCost.getReplaceCost(EditCost.convertToIndex(seq1.charAt(i-1)),EditCost.convertToIndex(seq2.charAt(j-1)));
int temp = insert < delete ? insert:delete;
int min = temp < replace ? temp:replace;// 取3个的最小值
dp[i][j] = min;
}
}
}
return dp[lenseq1][lenseq2];
// END YOUR CODE
}
}