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 1619) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/AlignmentAlgorithm.java (revision 1620) @@ -6,6 +6,4 @@ public interface AlignmentAlgorithm { - - public abstract void align(int[] input1, int[] input2, SubstitutionMatrix submat,float threshold); /** @@ -20,5 +18,8 @@ public abstract void printAlignment(); - public abstract ArrayList> getMatches(); + public abstract ArrayList getMatches(); + + void align(NumberSequence input1, NumberSequence input2, + SubstitutionMatrix submat, float threshold); } Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/GenerateTask.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/GenerateTask.java (revision 1620) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/GenerateTask.java (revision 1620) @@ -0,0 +1,34 @@ +package de.ugoe.cs.autoquest.tasktrees.alignment.algorithms; + +import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration; +import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequence; +import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskBuilder; +import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskFactory; + +public class GenerateTask { + + + private ITaskFactory taskFactory; + /** + *

+ * the task builder to be used for creating substructures for the temporal + * relationships identified during rule application + *

+ */ + private ITaskBuilder taskBuilder; + + void sequence() { + ISequence sequence = taskFactory.createNewSequence(); + //taskBuilder.addChild(sequence,ITask); + + } + + + void iteration() { + IIteration iteration = taskFactory.createNewIteration(); + //taskBuilder.setMarkedTask(iteration, child); + } + + + +} Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/Match.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/Match.java (revision 1620) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/Match.java (revision 1620) @@ -0,0 +1,43 @@ +package de.ugoe.cs.autoquest.tasktrees.alignment.algorithms; + +import java.util.ArrayList; +import java.util.LinkedList; + +public class Match { + private ArrayList matchseqs; + + private LinkedList occurences; + + + Match(){ + matchseqs = new ArrayList(2); + occurences = new LinkedList(); + matchseqs.add(null); + matchseqs.add(null); + } + + public NumberSequence getFirstSequence() { + return matchseqs.get(0); + } + + public NumberSequence getSecondSequence() { + return matchseqs.get(1); + } + + public void setFirstSequence(NumberSequence seq) { + matchseqs.set(0, seq); + } + + public void setSecondSequence(NumberSequence seq) { + matchseqs.set(1, seq); + } + + public void addOccurence(MatchOccurence occurence) { + occurences.add(occurence); + } + + public int occurenceCount() { + return occurences.size(); + } + +} Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/MatchOccurence.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/MatchOccurence.java (revision 1620) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/MatchOccurence.java (revision 1620) @@ -0,0 +1,19 @@ +package de.ugoe.cs.autoquest.tasktrees.alignment.algorithms; + +public class MatchOccurence { + private int startindex; + private int sequenceId; + public MatchOccurence(int startindex, int sequenceId) { + this.startindex = startindex; + this.sequenceId = sequenceId; + } + public int getStartindex() { + return startindex; + } + public void setStartindex(int startindex) { + this.startindex = startindex; + } + public int getSequenceId() { + return sequenceId; + } +} 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 1619) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/NeedlemanWunsch.java (revision 1620) @@ -260,5 +260,5 @@ @Override - public ArrayList> getMatches() { + public ArrayList getMatches() { // TODO Auto-generated method stub return null; @@ -266,10 +266,10 @@ @Override - public void align(int[] input1, int[] input2, SubstitutionMatrix submat, + public void align(NumberSequence input1, NumberSequence input2, SubstitutionMatrix submat, float threshold) { - this.input1 = input1; - this.input2 = input2; - length1 = input1.length; - length2 = input2.length; + this.input1 = input1.getSequence(); + this.input2 = input2.getSequence(); + length1 = input1.size(); + length2 = input2.size(); this.submat = submat; Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/NumberSequence.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/NumberSequence.java (revision 1619) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/NumberSequence.java (revision 1620) @@ -6,5 +6,20 @@ public class NumberSequence { private int[] sequence; - private int signature; + private int id; + + public ArrayList getMatches() { + return matches; + } + + + public void setMatches(ArrayList matches) { + this.matches = matches; + } + + public void addMatches(ArrayList matches) { + this.matches.addAll(matches); + } + + private ArrayList matches; public NumberSequence(int size) { @@ -12,5 +27,5 @@ sequence = new int[size]; } - + public int[] getSequence() { return sequence; @@ -21,11 +36,5 @@ } - public int getSignature() { - return signature; - } - - public void setSignature(int signature) { - this.signature = signature; - } + public void printSequence() { @@ -38,4 +47,5 @@ public NumberSequence shuffle() { NumberSequence result = new NumberSequence(sequence.length); + result.setId(getId()); result.setSequence(this.sequence); Random rgen = new Random(); @@ -51,18 +61,30 @@ } - // TODO: This can be done faster - public int containsPattern(ArrayList pattern) { + + public int containsPattern(Match pattern) { int i = 0; int count = 0; - int[] pat1 = pattern.get(0).getSequence(); - int[] pat2 = pattern.get(1).getSequence(); + int[] pat1 = pattern.getFirstSequence().getSequence(); + int[] pat2 = pattern.getSecondSequence().getSequence(); notmatched: while (i < sequence.length - pat1.length) { if (sequence[i] == pat1[0] || sequence[i] == pat2[0]) { - for (int j = 0; j < pat1.length; j++) { - if (sequence[i + j] != pat1[j] - && sequence[i + j] != pat2[j]) { + int ipat1 =0; + int ipat2 =0; + while(ipat1 < pat1.length && ipat2> getMatches() { + public ArrayList getMatches() { // TODO Auto-generated method stub return null; @@ -271,10 +271,10 @@ @Override - public void align(int[] input1, int[] input2, SubstitutionMatrix submat, + public void align(NumberSequence input1, NumberSequence input2, SubstitutionMatrix submat, float threshold) { - this.input1 = input1; - this.input2 = input2; - length1 = input1.length; - length2 = input2.length; + this.input1 = input1.getSequence(); + this.input2 = input2.getSequence(); + length1 = input1.size(); + length2 = input2.size(); this.submat = submat; 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 1619) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/SmithWatermanRepeated.java (revision 1620) @@ -231,7 +231,9 @@ ns1.setSequence(reversed1); ns2.setSequence(reversed2); - - alignment.add(ns1); - alignment.add(ns2); + ns1.setId(alignment.get(0).getId()); + ns2.setId(alignment.get(1).getId()); + + alignment.set(0, ns1); + alignment.set(1, ns2); } @@ -272,6 +274,6 @@ } - public ArrayList> getMatches() { - ArrayList> result = new ArrayList>(); + public ArrayList getMatches() { + ArrayList result = new ArrayList(); //both alignment sequences should be equally long @@ -288,5 +290,5 @@ count++; } - //I am really missing memcpy here + //I am really missing memcpy here? How does one do this better in java? int[] tmp1 = new int[count]; int[] tmp2 = new int[count]; @@ -299,19 +301,14 @@ tmpns1.setSequence(tmp1); tmpns2.setSequence(tmp2); - ArrayList tmpal = new ArrayList(); - tmpal.add(tmpns1); - tmpal.add(tmpns2); + Match tmpal = new Match(); + tmpal.setFirstSequence(tmpns1); + tmpal.setSecondSequence(tmpns2); + tmpal.addOccurence(new MatchOccurence(start,alignment.get(0).getId())); + tmpal.addOccurence(new MatchOccurence(start,alignment.get(1).getId())); result.add(tmpal); } i++; } - - - - - - return result; - } @@ -354,10 +351,16 @@ @Override - public void align(int[] input1, int[] input2, SubstitutionMatrix submat, + public void align(NumberSequence input1, NumberSequence input2, SubstitutionMatrix submat, float threshold) { - this.input1 = input1; - this.input2 = input2; - length1 = input1.length; - length2 = input2.length; + + alignment = new ArrayList(); + alignment.add(input1); + alignment.add(input2); + + this.input1=input1.getSequence(); + this.input2=input2.getSequence(); + + length1 = input1.size(); + length2 = input2.size(); this.submat = submat; @@ -367,5 +370,5 @@ matrix = new MatrixEntry[length1+2][length2+1]; - alignment = new ArrayList(); + for (int i = 0; i <= length1+1; i++) { 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 1619) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/matrix/ObjectDistanceSubstitionMatrix.java (revision 1620) @@ -25,10 +25,10 @@ public ObjectDistanceSubstitionMatrix( - SymbolMap uniqueTasks,float positiveThreshold) { + SymbolMap uniqueTasks,float positiveThreshold, int gapPenalty) { this.uniqueTasks = uniqueTasks; this.positiveThreshold = positiveThreshold; idmapping = new HashMap(); matrix = new TriangleMatrix(uniqueTasks.size()+1); - gapPenalty = -3; + this.gapPenalty = gapPenalty; } 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 1619) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/matrix/PairwiseAlignmentGenerator.java (revision 1620) @@ -14,7 +14,9 @@ public static PairwiseAlignmentStorage generate( ArrayList numberseqs, - ObjectDistanceSubstitionMatrix submat) { + ObjectDistanceSubstitionMatrix submat, + int threshold) { PairwiseAlignmentStorage alignments = new PairwiseAlignmentStorage( numberseqs.size(), numberseqs.size()); + int smithWatermanThreshold = threshold; for (int i = 0; i < numberseqs.size(); i++) { @@ -25,7 +27,7 @@ if (i != j) { Console.traceln(Level.FINEST,"Aligning sequence " + i + " with sequence " + j); - int smithWatermanThreshold = 10; + AlignmentAlgorithm aa = AlignmentAlgorithmFactory.create(); - aa.align(ns1.getSequence(), ns2.getSequence(), submat, + aa.align(ns1, ns2, submat, smithWatermanThreshold); alignments.set(i, j, aa); @@ -33,14 +35,14 @@ AlignmentAlgorithm sameSequence1 = AlignmentAlgorithmFactory .create(); - sameSequence1.align(ns1.getSequence(), ns1.getSequence(), + sameSequence1.align(ns1, ns1, submat, smithWatermanThreshold); AlignmentAlgorithm sameSequence2 = AlignmentAlgorithmFactory .create(); - sameSequence2.align(ns2.getSequence(), ns2.getSequence(), + sameSequence2.align(ns2, ns2, submat, smithWatermanThreshold); AlignmentAlgorithm randomSequence = AlignmentAlgorithmFactory .create(); - randomSequence.align(ns1.shuffle().getSequence(), ns2 - .shuffle().getSequence(), submat, + randomSequence.align(ns1.shuffle(), ns2 + .shuffle(), submat, smithWatermanThreshold); 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 1619) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/UPGMAAligningTree.java (revision 1620) @@ -223,5 +223,5 @@ if(seqCount1 == 1 && seqCount2 == 1) { AlignmentAlgorithm aa = AlignmentAlgorithmFactory.create(); - aa.align(node1.getSequence(0).getSequence(), node2.getSequence(0).getSequence(), submat, 5); + aa.align(node1.getSequence(0), node2.getSequence(0), submat, 5); alignment = aa.getAlignment(); @@ -236,5 +236,5 @@ for(int i=0;i> matchseqs = new ArrayList>(); - PairwiseAlignmentStorage alignments = PairwiseAlignmentGenerator.generate(numberseqs,submat); + ArrayList matchseqs = new ArrayList(); + PairwiseAlignmentStorage alignments = PairwiseAlignmentGenerator.generate(numberseqs,submat,9); Console.traceln(Level.INFO,"retrieving significant sequence pieces"); @@ -167,6 +168,5 @@ for(int j=0; j< numberseqs.size();j++) { if(i != j) { - ArrayList> tmp = alignments.get(i, j).getMatches(); - matchseqs.addAll(tmp); + matchseqs.addAll(alignments.get(i, j).getMatches()); } } @@ -178,24 +178,30 @@ //search this match in every other sequence for(int i=0; i < matchseqs.size();i++) { - int occurencecount = 0; + int sequencecount = 0; + int totalcount = 0; + Match pattern = matchseqs.get(i); + + + + //Skip sequences with more 0 events (scrolls) than other events. Both of the pattern sequences are equally long, so the added 0 counts + //just need to be smaller than the length of one sequence + if(pattern.getFirstSequence().eventCount(0) + pattern.getSecondSequence().eventCount(0) +1 > pattern.getFirstSequence().size()) + continue; Console.traceln(Level.FINEST, "searching for patterns occuring most: " + Math.round((float)i/(float)matchseqs.size()*100) + "%"); - for(int j=0; j < matchseqs.size();j++) { - if(i>j) { - if(matchseqs.get(j).get(0).containsPattern(matchseqs.get(i)) > 0 || matchseqs.get(j).get(1).containsPattern(matchseqs.get(i)) > 0) { - occurencecount++; + for(int j=0; j < numberseqs.size();j++) { + int tmpcount = numberseqs.get(j).containsPattern(pattern); + if(tmpcount > 0) { + sequencecount++; + totalcount+=tmpcount; } - } - } - if(occurencecount > 1) { - System.out.println("Found pattern \n "); - matchseqs.get(i).get(0).printSequence(); - matchseqs.get(i).get(1).printSequence(); - System.out.println(occurencecount + " times"); + } + + if(totalcount > 1) { + matchseqs.get(i).getFirstSequence().printSequence(); + matchseqs.get(i).getFirstSequence().printSequence(); + System.out.println("Found pattern in " + sequencecount +"/" + numberseqs.size() + " sequences, total of " + totalcount + " occurences"); System.out.println(); } } - - - alignments = null; @@ -290,4 +296,5 @@ } } + templist.setId(numberseqs.size()); numberseqs.add(templist); comparator.clearBuffers();