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 1588) +++ branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/AlignmentAlgorithmFactory.java (revision 1589) @@ -9,6 +9,6 @@ //return new SmithWaterman(input1,input2,submat,threshold); - return new NeedlemanWunsch(input1,input2,submat,threshold); - //return new SmithWatermanRepeated(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/SmithWatermanRepeated.java =================================================================== --- branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/SmithWatermanRepeated.java (revision 1588) +++ branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/SmithWatermanRepeated.java (revision 1589) @@ -2,4 +2,6 @@ import java.util.ArrayList; +import java.util.Iterator; +import java.util.LinkedList; import java.util.logging.Level; @@ -216,46 +218,43 @@ } - - public void traceback() { MatrixEntry tmp = matrix[length1+1][0]; - int aligned1[] = new int[length1+1+length2+2]; - int aligned2[] = new int[length1+1+length2+2]; + LinkedList aligned1 = new LinkedList(); + LinkedList aligned2 = new LinkedList(); + do { + + aligned1.add(new Integer(tmp.getXvalue())); + aligned2.add(new Integer(tmp.getYvalue())); + + tmp = tmp.getPrevious(); + + } while (tmp != null); + + // reverse order of the alignment + int reversed1[] = new int[aligned1.size()]; + int reversed2[] = new int[aligned2.size()]; + int count = 0; - do - { - if(count != 0) - { - if (length1+1+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(); + for (Iterator it = aligned1.descendingIterator(); it.hasNext();) { 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]; - } - + reversed1[reversed1.length - count] = it.next(); + + } + count = 0; + for (Iterator it = aligned2.descendingIterator(); it.hasNext();) { + count++; + reversed2[reversed2.length - count] = it.next(); + } + 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() { 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 1588) +++ (revision ) @@ -1,37 +1,0 @@ -package de.ugoe.cs.autoquest.tasktrees.alignment.matrix; - - -import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithm; - -public class BinaryAlignmentStorage { - - private AlignmentAlgorithm[][] alignments; - UPGMAMatrix sequenceDistances; - - public BinaryAlignmentStorage(int sizex, int sizey) { - 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,AlignmentAlgorithm sw) { - alignments[i][j] = sw; - } - - public AlignmentAlgorithm get(int i,int j) { - return alignments[i][j]; - } - - public void setDistance(int i,int j,double distance) { - sequenceDistances.set(i, j, distance); - } - - public double getDistance(int i,int j) { - return sequenceDistances.get(i,j); - } - - public UPGMAMatrix getDistanceMatrix() { - return sequenceDistances; - } -} - Index: branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/matrix/PairwiseAlignmentGenerator.java =================================================================== --- branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/matrix/PairwiseAlignmentGenerator.java (revision 1589) +++ branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/matrix/PairwiseAlignmentGenerator.java (revision 1589) @@ -0,0 +1,67 @@ +package de.ugoe.cs.autoquest.tasktrees.alignment.matrix; + +import java.util.ArrayList; + +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; + +public class PairwiseAlignmentGenerator { + + + public static PairwiseAlignmentStorage generate(ArrayList numberseqs,ObjectDistanceSubstitionMatrix submat) { + PairwiseAlignmentStorage alignments = new PairwiseAlignmentStorage(numberseqs.size(),numberseqs.size()); + + for (int i = 0; i < numberseqs.size(); i++) { + NumberSequence ns1 = numberseqs.get(i); + for (int j = 0; j < numberseqs.size(); j++) { + NumberSequence ns2 = numberseqs.get(j); + + if (i != j) { + int smithWatermanThreshold = 10; + + alignments.set(i, j,AlignmentAlgorithmFactory.create( + ns1.getSequence(), ns2.getSequence(), submat, + smithWatermanThreshold)); + + AlignmentAlgorithm sameSequence1 = AlignmentAlgorithmFactory.create( + ns1.getSequence(), ns1.getSequence(), submat, + smithWatermanThreshold); + AlignmentAlgorithm sameSequence2 = AlignmentAlgorithmFactory.create( + ns2.getSequence(), ns2.getSequence(), submat, + smithWatermanThreshold); + AlignmentAlgorithm randomSequence = AlignmentAlgorithmFactory.create( + ns1.shuffle().getSequence(),ns2.shuffle().getSequence(),submat,smithWatermanThreshold); + + // Score of the aligmnment + double score = alignments.get(i,j).getAlignmentScore(); + if(score > 0) { + System.out.println(); + alignments.get(i, j).printAlignment(); + System.out.println(); + } + // Scores of the sequence being aligned to itself (maximum score) + double sSelf1 = sameSequence1.getAlignmentScore(); + double sSelf2 = sameSequence2.getAlignmentScore(); + // Score of sequences shuffled before aligned + double sRand = randomSequence.getAlignmentScore(); + + double sMax = (sSelf1 + sSelf2) / 2; + double sEff = (score - sRand)/ (sMax - sRand); + if(sEff < 0) { + sEff = 0; + } + double distance = -Math.log(sEff); + + + if(!Double.isInfinite(distance) && !Double.isNaN(distance)) { + if(distance < alignments.getDistance(i, j)) { + alignments.setDistance(i,j,distance ); + } + } + } + } + } + return alignments; + } +} Index: branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/matrix/PairwiseAlignmentStorage.java =================================================================== --- branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/matrix/PairwiseAlignmentStorage.java (revision 1589) +++ branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/matrix/PairwiseAlignmentStorage.java (revision 1589) @@ -0,0 +1,42 @@ +package de.ugoe.cs.autoquest.tasktrees.alignment.matrix; + + + + +import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithm; + + +public class PairwiseAlignmentStorage { + + private AlignmentAlgorithm[][] alignments; + private UPGMAMatrix sequenceDistances; + + public PairwiseAlignmentStorage(int sizex, int sizey) { + 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,AlignmentAlgorithm sw) { + alignments[i][j] = sw; + } + + public AlignmentAlgorithm get(int i,int j) { + return alignments[i][j]; + } + + public void setDistance(int i,int j,double distance) { + sequenceDistances.set(i, j, distance); + } + + public double getDistance(int i,int j) { + return sequenceDistances.get(i,j); + } + + public UPGMAMatrix getDistanceMatrix() { + return sequenceDistances; + } +} + 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 1588) +++ branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/UPGMAAligningTree.java (revision 1589) @@ -15,11 +15,10 @@ 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; -import de.ugoe.cs.autoquest.tasktrees.alignment.matrix.BinaryAlignmentStorage; +import de.ugoe.cs.autoquest.tasktrees.alignment.matrix.PairwiseAlignmentStorage; import de.ugoe.cs.autoquest.tasktrees.alignment.matrix.ObjectDistanceSubstitionMatrix; import de.ugoe.cs.autoquest.tasktrees.alignment.matrix.UPGMAMatrix; @@ -48,5 +47,5 @@ * @param m distance matrix */ - public UPGMAAligningTree(ArrayList numberseqs, BinaryAlignmentStorage alignments, ObjectDistanceSubstitionMatrix submat) + public UPGMAAligningTree(ArrayList numberseqs, PairwiseAlignmentStorage alignments, ObjectDistanceSubstitionMatrix submat) { if (alignments.getDistanceMatrix().size() < 2) @@ -82,5 +81,5 @@ // private ArrayList numberseqs; - private BinaryAlignmentStorage alignments; + private PairwiseAlignmentStorage alignments; private ObjectDistanceSubstitionMatrix submat; private int numClusters; @@ -216,13 +215,5 @@ 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()); @@ -237,5 +228,5 @@ alignment.addAll(node1.getSequences()); - BinaryAlignmentStorage tempStorage = new BinaryAlignmentStorage(seqCount1,seqCount2); + PairwiseAlignmentStorage tempStorage = new PairwiseAlignmentStorage(seqCount1,seqCount2); double maxScore = 0.0; int maxIndex = 0; @@ -254,5 +245,5 @@ else if(seqCount1 == 1 && seqCount2 > 1) { alignment.addAll(node2.getSequences()); - BinaryAlignmentStorage tempStorage = new BinaryAlignmentStorage(seqCount1,seqCount2); + PairwiseAlignmentStorage tempStorage = new PairwiseAlignmentStorage(seqCount1,seqCount2); double maxScore = 0.0; int maxIndex = 0; @@ -270,6 +261,6 @@ //Align 2 groups else if((seqCount1 > 1) && (seqCount2 > 1)){ - BinaryAlignmentStorage tempStorage1 = new BinaryAlignmentStorage(seqCount2,1); - BinaryAlignmentStorage tempStorage2 = new BinaryAlignmentStorage(seqCount1,1); + PairwiseAlignmentStorage tempStorage1 = new PairwiseAlignmentStorage(seqCount2,1); + PairwiseAlignmentStorage tempStorage2 = new PairwiseAlignmentStorage(seqCount1,1); double maxScore1 = 0.0; double maxScore2 = 0.0; @@ -334,4 +325,12 @@ (oc[aj]/ocsum)*jdist; } + + + public void printMultipleAlignment() { + for (Iterator it = getRoot().getSequences().iterator(); it.hasNext();) { + NumberSequence tmp = it.next(); + tmp.printSequence(); + } + } } 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 1588) +++ branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRuleAlignment.java (revision 1589) @@ -29,5 +29,6 @@ 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.matrix.BinaryAlignmentStorage; +import de.ugoe.cs.autoquest.tasktrees.alignment.matrix.PairwiseAlignmentGenerator; +import de.ugoe.cs.autoquest.tasktrees.alignment.matrix.PairwiseAlignmentStorage; import de.ugoe.cs.autoquest.tasktrees.alignment.matrix.ObjectDistanceSubstitionMatrix; import de.ugoe.cs.autoquest.tasktrees.alignment.pal.tree.UPGMAAligningTree; @@ -158,62 +159,12 @@ submat.generate(); + + PairwiseAlignmentStorage alignments = PairwiseAlignmentGenerator.generate(numberseqs,submat); - BinaryAlignmentStorage alignments = new BinaryAlignmentStorage(numberseqs.size(),numberseqs.size()); - - - for (int i = 0; i < numberseqs.size(); i++) { - NumberSequence ns1 = numberseqs.get(i); - for (int j = 0; j < numberseqs.size(); j++) { - NumberSequence ns2 = numberseqs.get(j); - - if (i != j) { - int smithWatermanThreshold = 10; - - alignments.set(i, j,AlignmentAlgorithmFactory.create( - ns1.getSequence(), ns2.getSequence(), submat, - smithWatermanThreshold)); - AlignmentAlgorithm sameSequence1 = AlignmentAlgorithmFactory.create( - ns1.getSequence(), ns1.getSequence(), submat, - smithWatermanThreshold); - AlignmentAlgorithm sameSequence2 = AlignmentAlgorithmFactory.create( - ns2.getSequence(), ns2.getSequence(), submat, - smithWatermanThreshold); - AlignmentAlgorithm randomSequence = AlignmentAlgorithmFactory.create( - ns1.shuffle().getSequence(),ns2.shuffle().getSequence(),submat,smithWatermanThreshold); - - // Score of the aligmnment - double score = alignments.get(i,j).getAlignmentScore(); - // Scores of the sequence being aligned to itself (maximum score) - double sSelf1 = sameSequence1.getAlignmentScore(); - double sSelf2 = sameSequence2.getAlignmentScore(); - // Score of sequences shuffled before aligned - double sRand = randomSequence.getAlignmentScore(); - - double sMax = (sSelf1 + sSelf2) / 2; - double sEff = (score - sRand)/ (sMax - sRand); - if(sEff < 0) { - sEff = 0; - } - double distance = -Math.log(sEff); - - - if(!Double.isInfinite(distance) && !Double.isNaN(distance)) { - if(distance < alignments.getDistance(i, j)) { - alignments.setDistance(i,j,distance ); - } - } - } - } - } - //alignments.get(20, 47).printDPMatrix(); - //alignments.get(20, 47).printAlignment(); System.out.println(alignments.getDistanceMatrix()); - UPGMAAligningTree guidetree = new UPGMAAligningTree(numberseqs, alignments,submat); - 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(); - } + //UPGMAAligningTree guidetree = new UPGMAAligningTree(numberseqs, alignments,submat); + +