Changeset 1559 for branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/SmithWatermanRepeated.java

Timestamp:

06/04/14 16:42:02 (10 years ago)

Author:

rkrimmel

Message:

Further adjustments of the smithWatermanRepeated algorithm

File:

• branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/SmithWatermanRepeated.java (modified) (9 diffs)

branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/SmithWatermanRepeated.java

@@ -51 +51 @@
                 matrix = new MatrixEntry[length1+2][length2+1];
                 
-                for (int i = 0; i <= length1; i++) {
+                for (int i = 0; i <= length1+1; i++) {
                         for(int j = 0; j< length2; j++) {
                                 matrix[i][j] = new MatrixEntry();
@@ -71 +71 @@
          * @return Cost of substitution of the character in str1 by the one in str2
          */
-        private float similarity(int i, int j) {
-                if (i == 0 || j == 0) {
-                        // it's a gap 
-                        return submat.getGapPenalty();
-                }
-                // System.out.println("Diag letters: " + input1[i-1] + " " +
-                // input2[j-1]);
-                // return (input1[i - 1] == input2[j - 1]) ? MATCH_SCORE :
-                // MISMATCH_SCORE;
+        private float similarity(int i, int j) { 
                 return submat.getDistance(input1[i - 1], input2[j - 1]);
         }
 
         /**
-         * Build the score matrix using dynamic programming. Note: The indel scores
-         * must be negative. Otherwise, the part handling the first row and column
-         * has to be modified.
+         * Build the score matrix using dynamic programming.
          */
         private void buildMatrix() {
@@ -93 +83 @@
                 }
                 
-
-                // base case
+                // it's a gap
                 matrix[0][0].setScore(0);
                 matrix[0][0].setPrevious(null); // starting point
@@ -107 +96 @@
                 
                 
-                for (int i = 1; i <= length1; i++) {
+                for (int i = 1; i <= length1 + 1; i++) {
                 
                         // Formula for first row:
@@ -113 +102 @@
                         
                         float firstRowLeftScore = matrix[i-1][0].getScore();
-                        float tempMax = matrix[i-1][1].getScore();
-                        
-                        //position of the maximal score of the previous row
-                        int maxRowIndex = 1;
-                        
-                        for(int j = 2; j < length2;j++) {
-                                if(matrix[i-1][j].getScore() > tempMax) {
-                                        tempMax = matrix[i-1][j].getScore();
-                                        maxRowIndex = j;
-                                }
-                        }
-                        
+                        //for sequences of length 1
+                        float tempMax;
+                        int maxRowIndex;
+                        if(length2 == 1) {
+                                tempMax = matrix[i-1][0].getScore();
+                                maxRowIndex = 0;
+                        } else {
+                                tempMax = matrix[i-1][1].getScore();
+                                maxRowIndex = 1;
+                                //position of the maximal score of the previous row
+                                
+                                for(int j = 2; j < length2;j++) {
+                                        if(matrix[i-1][j].getScore() > tempMax) {
+                                                tempMax = matrix[i-1][j].getScore();
+                                                maxRowIndex = j;
+                                        }
+                                }
+
+                        }
+                        
+                                        
                         tempMax -= scoreThreshold;
                         matrix[i][0].setScore(Math.max(firstRowLeftScore, tempMax));
+                        if(tempMax ==matrix[i][0].getScore()){
+                                matrix[i][0].setPrevious(matrix[i-1][maxRowIndex]);
+                        }
+                        
+                        if(firstRowLeftScore == matrix[i][0].getScore()) {
+                                matrix[i][0].setPrevious(matrix[i-1][0]);
+                        }
+                        
+                        //The last additional score is not related to a character in the input sequence, it's the total score. Therefore we don't need to save something for it
+                        if(i<length1+1) 
+                        {
+                                matrix[i][0].setXvalue(input1[i-1]);
+                                matrix[i][0].setYvalue(-2);
+                                
+                        }
+                        else { 
+                        //End after we calculated final score
+                                return;
+                        }
                         
                         
                         for (int j = 1; j < length2; j++) {
                                 float diagScore = matrix[i - 1][j - 1].getScore() + similarity(i, j);
-                                float upScore = matrix[i][j - 1].getScore() + similarity(0, j);
-                                float leftScore = matrix[i - 1][j].getScore() + similarity(i, 0);
+                                float upScore = matrix[i][j - 1].getScore() + submat.getGapPenalty();
+                                float leftScore = matrix[i - 1][j].getScore() + submat.getGapPenalty();
 
                                 matrix[i][j].setScore(Math.max(diagScore,Math.max(upScore, Math.max(leftScore,matrix[i][0].getScore()))));
@@ -138 +155 @@
                                 // find the directions that give the maximum scores.
                                 // Multiple directions are ignored TODO
+                                //True if we had a match
                                 if (diagScore == matrix[i][j].getScore()) {
                                         matrix[i][j].setPrevious(matrix[i-1][j-1]);
-                                }
+                                        matrix[i][j].setXvalue(input1[i-1]);
+                                        matrix[i][j].setYvalue(input2[j-1]);
+                                }
+                                //true if we took an event from sequence x and not from y
                                 if (leftScore == matrix[i][j].getScore()) {
+                                        matrix[i][j].setXvalue(input1[i-1]);
+                                        matrix[i][j].setYvalue(-1);
                                         matrix[i][j].setPrevious(matrix[i-1][j]);
                                 }
+                                //true if we took an event from sequence y and not from x
                                 if (upScore == matrix[i][j].getScore()) {
+                                        matrix[i][j].setXvalue(-1);
+                                        matrix[i][j].setYvalue(input2[j-1]);
                                         matrix[i][j].setPrevious(matrix[i][j-1]);
                                 }
+                                //true if we ended a matching region 
                                 if (matrix[i][0].getScore() == matrix[i][j].getScore()) {
-                                        matrix[i][j].setPrevious(matrix[i-1][maxRowIndex]);
-                                }
-                        }
+                                        matrix[i][j].setPrevious(matrix[i][0]);
+                                        matrix[i][j].setXvalue(input1[i-1]);
+                                        matrix[i][j].setYvalue(-2);
+                                }
+                        }
+                        
+                        //Set the complete score cell
+                        
                 }
         }
@@ -175 +207 @@
          * Get the alignment score between the two input strings.
          */
-        public double getAlignmentScore() {
-                return getMaxScore();
+        public float getAlignmentScore() {
+                return matrix[length1+1][0].getScore();
         }
 
@@ -188 +220 @@
          */
         private int[] traceback(int i, int j) {
-
+                
+                        
                 return null;
         }
+        
+        public void traceback() {
+                MatrixEntry tmp = matrix[length1+1][0];
+                String aligned1 = "";
+                String aligned2 = "";
+                int count = 0;
+                do
+                {
+                        String append1="";
+                        String append2="";
+                                        
+                        if(tmp.getXvalue() == -1) {
+                                append1 = "  ___";
+                        }
+                        else if(tmp.getXvalue() == -2) {
+                                append1 = "  ...";
+                        }
+                        else {
+                                append1 = String.format("%5d", tmp.getXvalue());
+                        }
+
+                        if(tmp.getYvalue() == -1) {
+                                append2 = "  ___";
+                        }
+                        else if(tmp.getYvalue() == -2) {
+                                append2 = "  ...";
+                        }
+                        else {
+                                append2 = String.format("%5d", tmp.getYvalue());
+                        }
+                        if(count != 0)
+                        {
+                                aligned1 = append1 + aligned1;
+                                aligned2 = append2 + aligned2;
+                        }
+                        
+                        tmp = tmp.getPrevious();
+                        count++;
+                        
+                } while(tmp != null);
+                System.out.println(aligned1);
+                System.out.println(aligned2);
+        }
+        
 
         
@@ -207 +284 @@
                                 System.out.print("      ");
                         }
-                        for (int i = 0; i <= length1; i++) {
-                                System.out.format("%4.1f ",matrix[i][j].getScore());
-                        }
+                        for (int i = 0; i <= length1 + 1; i++) {
+                                if((i<length1+1) || (i==length1+1 && j==0))     {
+                                        System.out.format("%4.1f ",matrix[i][j].getScore());
+                                }
+                                
+                        }                       
                         System.out.println();
                 }