Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/AlignmentAlgorithm.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/AlignmentAlgorithm.java (revision 1586) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/AlignmentAlgorithm.java (revision 1586) @@ -0,0 +1,14 @@ +package de.ugoe.cs.autoquest.tasktrees.alignment.algorithms; + +import java.util.ArrayList; + +public interface AlignmentAlgorithm { + + /** + * Get the alignment score between the two input strings. + */ + public abstract double getAlignmentScore(); + + public abstract ArrayList getAlignment(); + +} Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/AlignmentAlgorithmFactory.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/AlignmentAlgorithmFactory.java (revision 1586) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/AlignmentAlgorithmFactory.java (revision 1586) @@ -0,0 +1,12 @@ +package de.ugoe.cs.autoquest.tasktrees.alignment.algorithms; + +import de.ugoe.cs.autoquest.tasktrees.alignment.matrix.SubstitutionMatrix; + +public class AlignmentAlgorithmFactory { + + + public static AlignmentAlgorithm create(int[] input1, int[] input2, SubstitutionMatrix submat,float threshold) { + + return new SmithWaterman(input1,input2,submat,threshold); + } +} Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/SmithWaterman.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/SmithWaterman.java (revision 1586) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/SmithWaterman.java (revision 1586) @@ -0,0 +1,293 @@ +package de.ugoe.cs.autoquest.tasktrees.alignment.algorithms; + +import java.util.ArrayList; +import java.util.logging.Level; + +import de.ugoe.cs.autoquest.tasktrees.alignment.matrix.SubstitutionMatrix; +import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.Constants; +import de.ugoe.cs.util.console.Console; + +public class SmithWaterman implements AlignmentAlgorithm { + + /** + * The first input + */ + private int[] input1; + + /** + * The second input String + */ + private int[] input2; + + /** + * The lengths of the input + */ + private int length1, length2; + + /** + * The score matrix. The true scores should be divided by the normalization + * factor. + */ + private MatrixEntry[][] matrix; + + private ArrayList alignment; + + private float scoreThreshold; + + /** + * Substitution matrix to calculate scores + */ + private SubstitutionMatrix submat; + + public SmithWaterman(int[] input1, int[] input2, SubstitutionMatrix submat, + float threshold) { + this.input1 = input1; + this.input2 = input2; + length1 = input1.length; + length2 = input2.length; + this.submat = submat; + + // System.out.println("Starting SmithWaterman algorithm with a " + // + submat.getClass() + " Substitution Matrix: " + + // submat.getClass().getCanonicalName()); + this.scoreThreshold = threshold; + + matrix = new MatrixEntry[length1 + 1][length2 + 1]; + alignment = new ArrayList(); + + for (int i = 0; i < length1+1; i++) { + for (int j = 0; j < length2+1; j++) { + matrix[i][j] = new MatrixEntry(); + } + } + + buildMatrix(); + traceback(); + } + + /** + * Compute the similarity score of substitution The position of the first + * character is 1. A position of 0 represents a gap. + * + * @param i + * Position of the character in str1 + * @param j + * Position of the character in str2 + * @return Cost of substitution of the character in str1 by the one in str2 + */ + private double similarity(int i, int j) { + return submat.getScore(input1[i - 1], input2[j - 1]); + } + + /** + * Build the score matrix using dynamic programming. + */ + private void buildMatrix() { + if (submat.getGapPenalty() >= 0) { + throw new Error("Indel score must be negative"); + } + + // it's a gap + matrix[0][0].setScore(0); + matrix[0][0].setPrevious(null); // starting point + + // the first column + for (int j = 1; j < length2+1; j++) { + matrix[0][j].setScore(0); + matrix[0][j].setPrevious(matrix[0][j - 1]); + matrix[0][j].setYvalue(input2[j]); + matrix[0][j].setXvalue(Constants.GAP_SYMBOL); + } + // the first row + + for (int j = 1; j < length1+1; j++) { + matrix[j][0].setScore(0); + matrix[j][0].setPrevious(matrix[j - 1][0]); + matrix[j][0].setXvalue(input1[j]); + matrix[j][0].setYvalue(Constants.GAP_SYMBOL); + } + + for (int i = 1; i < length1; i++) { + + for (int j = 1; j < length2; j++) { + double diagScore = matrix[i - 1][j - 1].getScore() + + similarity(i, j); + double upScore = matrix[i][j - 1].getScore() + + submat.getGapPenalty(); + double leftScore = matrix[i - 1][j].getScore() + + submat.getGapPenalty(); + + matrix[i][j].setScore(Math.max(diagScore, + Math.max(upScore, Math.max(leftScore, 0)))); + + // find the directions that give the maximum scores. + // TODO: Multiple directions are ignored, we choose the first + // maximum score + // 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(Constants.GAP_SYMBOL); + 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(Constants.GAP_SYMBOL); + matrix[i][j].setYvalue(input2[j - 1]); + matrix[i][j].setPrevious(matrix[i][j - 1]); + } + if (0 == matrix[i][j].getScore()) { + matrix[i][j].setPrevious(matrix[0][0]); + matrix[i][j].setXvalue(-2); + matrix[i][j].setYvalue(-2); + } + } + + // Set the complete score cell + + } + } + + /** + * Get the maximum value in the score matrix. + */ + public double getMaxScore() { + double maxScore = 0; + + // skip the first row and column + for (int i = 1; i <= length1; i++) { + for (int j = 1; j < length2; j++) { + if (matrix[i][j].getScore() > maxScore) { + maxScore = matrix[i][j].getScore(); + } + } + } + + return maxScore; + } + + /* + * (non-Javadoc) + * + * @see + * de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithm + * #getAlignmentScore() + */ + @Override + public double getAlignmentScore() { + return getMaxScore(); + } + + public void traceback() { + MatrixEntry tmp = matrix[length1][length2]; + int aligned1[] = new int[length1 + length2 + 2]; + int aligned2[] = new int[length1 + length2 + 2]; + int count = 0; + do { + if (length1 + length2 + 2 == count) { + Console.traceln(Level.WARNING, + "Traceback longer than both sequences summed up!"); + break; + } + aligned1[count] = tmp.getXvalue(); + aligned2[count] = tmp.getYvalue(); + + tmp = tmp.getPrevious(); + count++; + + } while (tmp != null); + count--; + // reverse order of the alignment + int reversed1[] = new int[count]; + int reversed2[] = new int[count]; + + for (int i = count - 1; i > 0; i--) { + reversed1[reversed1.length - i] = aligned1[i]; + reversed2[reversed2.length - i] = aligned2[i]; + } + + NumberSequence ns1 = new NumberSequence(reversed1.length); + NumberSequence ns2 = new NumberSequence(reversed2.length); + ns1.setSequence(reversed1); + ns2.setSequence(reversed2); + + alignment.add(ns1); + alignment.add(ns2); + } + + public void printAlignment() { + MatrixEntry tmp = matrix[length1 + 1][0]; + String aligned1 = ""; + String aligned2 = ""; + int count = 0; + do { + String append1 = ""; + String append2 = ""; + + if (tmp.getXvalue() == Constants.GAP_SYMBOL) { + append1 = " ___"; + } else { + append1 = String.format("%5d", tmp.getXvalue()); + } + + if (tmp.getYvalue() == Constants.GAP_SYMBOL) { + 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); + } + + /** + * print the dynmaic programming matrix + */ + public void printDPMatrix() { + System.out.print(" "); + for (int i = 1; i <= length1; i++) + System.out.format("%5d", input1[i - 1]); + System.out.println(); + for (int j = 0; j < length2; j++) { + if (j > 0) + System.out.format("%5d ", input2[j - 1]); + else { + System.out.print(" "); + } + for (int i = 0; i < length1; i++) { + System.out.format("%4.1f ", matrix[i][j].getScore()); + } + System.out.println(); + } + } + + /* + * (non-Javadoc) + * + * @see + * de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithm + * #getAlignment() + */ + @Override + public ArrayList getAlignment() { + return alignment; + } + + public void setAlignment(ArrayList alignment) { + this.alignment = alignment; + } + +} Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/SmithWatermanRepeated.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/SmithWatermanRepeated.java (revision 1585) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/SmithWatermanRepeated.java (revision 1586) @@ -8,5 +8,5 @@ import de.ugoe.cs.util.console.Console; -public class SmithWatermanRepeated { +public class SmithWatermanRepeated implements AlignmentAlgorithm { /** @@ -208,7 +208,8 @@ } - /** - * Get the alignment score between the two input strings. - */ + /* (non-Javadoc) + * @see de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithm#getAlignmentScore() + */ + @Override public double getAlignmentScore() { return matrix[length1+1][0].getScore(); @@ -328,4 +329,8 @@ + /* (non-Javadoc) + * @see de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithm#getAlignment() + */ + @Override public ArrayList getAlignment() { return alignment; Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/matrix/BinaryAlignmentStorage.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/matrix/BinaryAlignmentStorage.java (revision 1585) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/matrix/BinaryAlignmentStorage.java (revision 1586) @@ -2,22 +2,22 @@ -import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.SmithWatermanRepeated; +import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithm; public class BinaryAlignmentStorage { - private SmithWatermanRepeated[][] alignments; + private AlignmentAlgorithm[][] alignments; UPGMAMatrix sequenceDistances; public BinaryAlignmentStorage(int sizex, int sizey) { - alignments = new SmithWatermanRepeated[sizex+1][sizey+1]; + alignments = new AlignmentAlgorithm[sizex+1][sizey+1]; sequenceDistances = new UPGMAMatrix(Math.max(sizex,sizey)); sequenceDistances.initialize(Double.POSITIVE_INFINITY); } - public void set(int i,int j,SmithWatermanRepeated sw) { + public void set(int i,int j,AlignmentAlgorithm sw) { alignments[i][j] = sw; } - public SmithWatermanRepeated get(int i,int j) { + public AlignmentAlgorithm get(int i,int j) { return alignments[i][j]; } Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/FengDoolittleNode.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/FengDoolittleNode.java (revision 1585) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/FengDoolittleNode.java (revision 1586) @@ -11,9 +11,7 @@ import java.util.ArrayList; -import java.util.logging.Level; - import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.NumberSequence; import de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc.Identifier; -import de.ugoe.cs.util.console.Console; + @@ -374,5 +372,4 @@ newNode.addChild(child2); newNode.setIdentifier(new Identifier(child1.getIdentifier().getName() + " " + child2.getIdentifier().getName())); - //System.out.println("Merging " + child1.getIdentifier() + " with " + child2.getIdentifier()); return newNode; Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/UPGMAAligningTree.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/UPGMAAligningTree.java (revision 1585) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/UPGMAAligningTree.java (revision 1586) @@ -15,7 +15,8 @@ import java.util.ArrayList; -import java.util.Iterator; import java.util.logging.Level; +import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithm; +import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithmFactory; import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.NumberSequence; import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.SmithWatermanRepeated; @@ -228,5 +229,5 @@ int maxIndex = 0; for(int i=0;i 0) alignment.add(tempStorage.get(maxIndex, 1).getAlignment().get(1)); } @@ -243,5 +245,5 @@ int maxIndex = 0; for(int i=0;i 0) alignment.add(tempStorage.get(1,maxIndex).getAlignment().get(1)); } @@ -261,5 +264,5 @@ for(int i=0;i 0) alignment.add(tempStorage1.get(maxIndex1,0).getAlignment().get(0)); } for(int i=0; i 0) alignment.add(tempStorage2.get(maxIndex2,0).getAlignment().get(0)); } Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRuleAlignment.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRuleAlignment.java (revision 1585) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRuleAlignment.java (revision 1586) @@ -26,4 +26,6 @@ import java.util.logging.Level; +import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithm; +import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithmFactory; import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.NumberSequence; import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.SmithWatermanRepeated; @@ -170,14 +172,14 @@ int smithWatermanThreshold = 10; - alignments.set(i, j,new SmithWatermanRepeated( + alignments.set(i, j,AlignmentAlgorithmFactory.create( ns1.getSequence(), ns2.getSequence(), submat, smithWatermanThreshold)); - SmithWatermanRepeated sameSequence1 = new SmithWatermanRepeated( + AlignmentAlgorithm sameSequence1 = AlignmentAlgorithmFactory.create( ns1.getSequence(), ns1.getSequence(), submat, smithWatermanThreshold); - SmithWatermanRepeated sameSequence2 = new SmithWatermanRepeated( + AlignmentAlgorithm sameSequence2 = AlignmentAlgorithmFactory.create( ns2.getSequence(), ns2.getSequence(), submat, smithWatermanThreshold); - SmithWatermanRepeated randomSequence = new SmithWatermanRepeated( + AlignmentAlgorithm randomSequence = AlignmentAlgorithmFactory.create( ns1.shuffle().getSequence(),ns2.shuffle().getSequence(),submat,smithWatermanThreshold);