The Needleman–Wunsch algorithm performs a global alignment on two sequences (called A and B here). It is commonly used in bioinformatics to align protein or nucleotide sequences. The Smith-Waterman algorithm is a well-known algorithm for performing local sequence alignment; that is, for determining similar regions between two nucleotide or protein sequences. Instead of looking at the total sequence, the Smith-Waterman algorithm compares segments of all possible lengths and optimizes the similarity measure.For the details, see the code as follow:
Needleman–Wunsch algorithm public void NW(String f1, String f2) { // implement of Needleman–Wunsch algorithm; int [][] score = new int [ 26 ][ 26 ]; // for the 26 English characters; SimMatrix(score); // forming similarity matrix and store it in score; String seq = " abcdeaghijklmnopqrstuvwxyz " ; // compare with the input string to form numbers; int [] seq1 = new int [f1.length()]; int [] seq2 = new int [f2.length()]; int i; int j; for (i = 0 ; i < f1.length(); i ++ ) { // changing the characters to the numbers for (j = 0 ; j < seq.length(); j ++ ) { // to read the score[][]; if (f1.charAt(i) == seq.charAt(j)) seq1[i] = j; } } for (i = 0 ; i < f2.length(); i ++ ) { for (j = 0 ; j < seq.length(); j ++ ) { // changing the characters to the numbers if (f2.charAt(i) == seq.charAt(j)) // to read the score[][]; seq2[i] = j; } } int gap = - 5 ; // defining gap penalty; int match, delete, insert; int [][] F = new int [f1.length() + 1 ][f2.length() + 1 ]; // forming F[][]; for (j = 0 ; j <= f2.length(); j ++ ) { F[ 0 ][j] = gap * j; } for (i = 0 ; i <= f1.length(); i ++ ) { F[i][ 0 ] = gap * i; } for (i = 1 ; i <= f1.length(); i ++ ) { // assigned the optimal score for the alignment; for (j = 1 ; j <= f2.length(); j ++ ) { match = F[i - 1 ][j - 1 ] + score[seq1[i - 1 ]][seq2[j - 1 ]]; delete = F[i - 1 ][j] + gap; insert = F[i][j - 1 ] + gap; if ((match > delete) && (match > insert)) { F[i][j] = match; } else if (delete > insert) { F[i][j] = delete; } else { F[i][j] = insert; } } } String Alignmentf1 = "" ; // tracing back the pathway; String Alignmentf2 = "" ; i = f1.length(); j = f2.length(); while ((i > 0 ) && (j > 0 )) { int Score = F[i][j]; int ScoreDiag = F[i - 1 ][j - 1 ]; // do not have to define ScoreUp, it will not be used; int ScoreLeft = F[i - 1 ][j]; if (Score == (ScoreDiag + score[seq1[i - 1 ]][seq2[j - 1 ]])) { Alignmentf1 = f1.charAt(i - 1 ) + Alignmentf1; Alignmentf2 = f2.charAt(j - 1 ) + Alignmentf2; i = i - 1 ; j = j - 1 ; } else if (Score == ScoreLeft + gap) { Alignmentf1 = f1.charAt(i - 1 ) + Alignmentf1; Alignmentf2 = " - " + Alignmentf2; i = i - 1 ; } else { Alignmentf1 = " - " + Alignmentf1; Alignmentf2 = f2.charAt(j - 1 ) + Alignmentf2; j = j - 1 ; } } while (i > 0 ) { Alignmentf1 = f1.charAt(i - 1 ) + Alignmentf1; Alignmentf2 = " - " + Alignmentf2; i = i - 1 ; } while (j > 0 ) { Alignmentf1 = " - " + Alignmentf1; Alignmentf2 = f2.charAt(j - 1 ) + Alignmentf2; j = j - 1 ; } System.out.println( " Global alignment score= " + F[f1.length()][f2.length()]); System.out.println( " Sequence1= " + Alignmentf1); System.out.println( " Sequence2= " + Alignmentf2); } public String readSequence(String file) { // read in the sequence from the text; String seq = "" ; String line = "" ; try { BufferedReader br = new BufferedReader( new FileReader(file)); while ((line = br.readLine()) != null ) { seq = seq + line; } } catch (FileNotFoundException e) { e.printStackTrace(); } catch (IOException e) { e.printStackTrace(); } return seq; }
Smith–Waterman algorithm public void SW(String f1, String f2) { int i, j, m; int match, mismatch, delete, insert; int w = 2 ; int gap =- 1 ; int [][] H = new int [f1.length() + 1 ][f2.length() + 1 ]; int max = 0 ; int line = 0 , colum = 0 ; for (j = 0 ; j <= f2.length(); j ++ ) { H[ 0 ][j] = 0 ; } for (i = 0 ; i <= f1.length(); i ++ ) { H[i][ 0 ] = 0 ; } for (i = 1 ; i <= f1.length(); i ++ ) { // assigned the optimal score for the alignment; for (j = 1 ; j <= f2.length(); j ++ ) { match = H[i - 1 ][j - 1 ] + w; mismatch = H[i - 1 ][j - 1 ] + gap; delete = H[i - 1 ][j] + gap; insert = H[i][j - 1 ] + gap; if (f1.charAt(i - 1 ) == f2.charAt(j - 1 )) { m = match; } else { m = mismatch; } if ((m > delete) && (m > insert) && (m > 0 )) { H[i][j] = m; } else if ((delete > insert) && (delete > 0 )) { H[i][j] = delete; } else if (insert > 0 ) { H[i][j] = insert; } else { H[i][j] = 0 ; } } } System.out.println( " The matrix H[][]: " ); for (i = 0 ;i <= f1.length();i ++ ){ for (j = 0 ;j <= f2.length();j ++ ){ System.out.print(H[i][j] + " " ); // show the H[][] matrix; } System.out.println(); } String Alignmentf1 = "" ; // tracing back the pathway; String Alignmentf2 = "" ; for (i = 0 ;i <= f1.length();i ++ ){ for (j = 0 ;j <= f2.length();j ++ ){ if (H[i][j] > max){ max = H[i][j]; line = i; colum = j; } } } i = line; j = colum; while ((i > 0 ) && (j > 0 )) { int Score = H[i][j]; int ScoreDiag = H[i - 1 ][j - 1 ]; // do not have to define ScoreUp, it will not be used; int ScoreLeft = H[i - 1 ][j]; if (f1.charAt(i - 1 ) == f2.charAt(j - 1 )) { w = 2 ; } else { w = - 1 ; } if (Score == (ScoreDiag + w)) { Alignmentf1 = f1.charAt(i - 1 ) + Alignmentf1; Alignmentf2 = f2.charAt(j - 1 ) + Alignmentf2; i = i - 1 ; j = j - 1 ; } else if (Score == ScoreLeft + w) { Alignmentf1 = f1.charAt(i - 1 ) + Alignmentf1; Alignmentf2 = " - " + Alignmentf2; i = i - 1 ; } else { Alignmentf1 = " - " + Alignmentf1; Alignmentf2 = f2.charAt(j - 1 ) + Alignmentf2; j = j - 1 ; } } while (i > 0 ) { Alignmentf1 = f1.charAt(i - 1 ) + Alignmentf1; Alignmentf2 = " - " + Alignmentf2; i = i - 1 ; } while (j > 0 ) { Alignmentf1 = " - " + Alignmentf1; Alignmentf2 = f2.charAt(j - 1 ) + Alignmentf2; j = j - 1 ; } System.out.println( " Highest value in matrix H[][]= " + H[line][colum]); System.out.print( " The value is in line " + line + " , " ); System.out.println( " colum " + colum); System.out.println( " Sequence1= " + Alignmentf1); System.out.println( " Sequence2= " + Alignmentf2); }