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 1587) @@ -12,3 +12,7 @@ public abstract ArrayList getAlignment(); + public abstract void printDPMatrix(); + + public abstract void printAlignment(); + } 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 1587) @@ -8,5 +8,7 @@ public static AlignmentAlgorithm create(int[] input1, int[] input2, SubstitutionMatrix submat,float threshold) { - return new SmithWaterman(input1,input2,submat,threshold); + //return new NeedlemanWunsch(input1,input2,submat,threshold); + return new NeedlemanWunsch(input1,input2,submat,threshold); + //return new SmithWatermanRepeated(input1,input2,submat,threshold); } } Index: branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/NeedlemanWunsch.java =================================================================== --- branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/NeedlemanWunsch.java (revision 1587) +++ branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/NeedlemanWunsch.java (revision 1587) @@ -0,0 +1,284 @@ +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 NeedlemanWunsch 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; + + /** + * Substitution matrix to calculate scores + */ + private SubstitutionMatrix submat; + + public NeedlemanWunsch(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()); + + 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; j++) { + matrix[0][j].setScore(j*submat.getGapPenalty()); + matrix[0][j].setPrevious(matrix[0][j - 1]); + matrix[0][j].setYvalue(input2[j-1]); + matrix[0][j].setXvalue(Constants.GAP_SYMBOL); + } + // the first row + + for (int j = 1; j <= length1; j++) { + matrix[j][0].setScore(j*submat.getGapPenalty()); + matrix[j][0].setPrevious(matrix[j - 1][0]); + matrix[j][0].setXvalue(input1[j-1]); + 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]); + } + } + } + } + + /** + * 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; 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][length2]; + 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/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 1587) @@ -32,6 +32,4 @@ private ArrayList alignment; - - private float scoreThreshold; /** @@ -51,5 +49,4 @@ // + submat.getClass() + " Substitution Matrix: " + // submat.getClass().getCanonicalName()); - this.scoreThreshold = threshold; matrix = new MatrixEntry[length1 + 1][length2 + 1]; @@ -93,5 +90,5 @@ // the first column - for (int j = 1; j < length2+1; j++) { + for (int j = 1; j < length2; j++) { matrix[0][j].setScore(0); matrix[0][j].setPrevious(matrix[0][j - 1]); @@ -101,5 +98,5 @@ // the first row - for (int j = 1; j < length1+1; j++) { + for (int j = 1; j < length1; j++) { matrix[j][0].setScore(0); matrix[j][0].setPrevious(matrix[j - 1][0]); @@ -262,5 +259,5 @@ System.out.format("%5d", input1[i - 1]); System.out.println(); - for (int j = 0; j < length2; j++) { + for (int j = 0; j <= length2; j++) { if (j > 0) System.out.format("%5d ", input2[j - 1]); @@ -268,5 +265,5 @@ System.out.print(" "); } - for (int i = 0; i < length1; i++) { + for (int i = 0; i <= length1; i++) { System.out.format("%4.1f ", matrix[i][j].getScore()); } 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 1586) +++ branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/SmithWatermanRepeated.java (revision 1587) @@ -102,5 +102,5 @@ - for (int i = 1; i <= length1 + 1; i++) { + for (int i = 1; i < length1 + 2; i++) { // Formula for first row: @@ -220,6 +220,6 @@ public void traceback() { MatrixEntry tmp = matrix[length1+1][0]; - int aligned1[] = new int[length1+length2+2]; - int aligned2[] = new int[length1+length2+2]; + int aligned1[] = new int[length1+1+length2+2]; + int aligned2[] = new int[length1+1+length2+2]; int count = 0; do @@ -227,5 +227,5 @@ if(count != 0) { - if (length1+length2+2 == count) { + if (length1+1+length2+2 == count) { Console.traceln(Level.WARNING, "Traceback longer than both sequences summed up!"); break; @@ -312,5 +312,5 @@ System.out.format("%5d", input1[i - 1]); System.out.println(); - for (int j = 0; j < length2; j++) { + for (int j = 0; j <= length2; j++) { if (j > 0) System.out.format("%5d ",input2[j - 1]); Index: branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/matrix/ObjectDistanceSubstitionMatrix.java =================================================================== --- branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/matrix/ObjectDistanceSubstitionMatrix.java (revision 1586) +++ branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/matrix/ObjectDistanceSubstitionMatrix.java (revision 1587) @@ -29,5 +29,5 @@ idmapping = new HashMap(); matrix = new TriangleMatrix(uniqueTasks.size()+1); - gapPenalty = -3; + gapPenalty = -2; } 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 1586) +++ branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/UPGMAAligningTree.java (revision 1587) @@ -137,4 +137,5 @@ private void finish() { + this.getRoot().setSequences(alignSequences(this.getRoot())); distance = null; } @@ -215,4 +216,12 @@ int seqCount1 = node1.getSequences().size(); int seqCount2 = node2.getSequences().size(); + + for(int i = 0; i < seqCount1; i++) { + for(int j = 0; j < seqCount2; j++) { + node1.getSequence(i).printSequence(); + node2.getSequence(j).printSequence(); + } + } + Console.traceln(Level.INFO,"Merging node " + node1.getIdentifier() + " with " + node2.getIdentifier()); //Console.println("SeqCount1: " + seqCount1 + " seqCount2 " + seqCount2); @@ -220,4 +229,5 @@ if(seqCount1 == 1 && seqCount2 == 1) { alignment = (alignments.get(node1.getNumber(), node2.getNumber())).getAlignment(); + } //Align a sequence to a group @@ -236,4 +246,5 @@ } //if(maxScore > 0) + alignment.add(tempStorage.get(maxIndex, 1).getAlignment().get(1)); } @@ -252,4 +263,5 @@ } //if(maxScore > 0) + alignment.add(tempStorage.get(1,maxIndex).getAlignment().get(1)); } 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 1586) +++ branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRuleAlignment.java (revision 1587) @@ -208,11 +208,15 @@ } } - //System.out.println(sequenceDistances.toString()); + //alignments.get(20, 47).printDPMatrix(); + //alignments.get(20, 47).printAlignment(); + + System.out.println(alignments.getDistanceMatrix().toString()); UPGMAAligningTree guidetree = new UPGMAAligningTree(numberseqs, alignments,submat); - - for (Iterator it = guidetree.getRoot().getChild(0).getSequences().iterator(); it.hasNext();) { + //System.out.println("Number of sequences in root node: " + guidetree.getRoot().getSequences().size()); + for (Iterator it = guidetree.getRoot().getSequences().iterator(); it.hasNext();) { NumberSequence tmp = it.next(); tmp.printSequence(); } + /*