Ignore:
Timestamp:
06/18/14 08:59:41 (11 years ago)
Author:
rkrimmel
Message:

Building distance matrix between sequences

Location:
branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees
Files:
9 edited

Legend:

Unmodified
Added
Removed

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

    r1559 r1568  
    22 
    33public class MatrixEntry { 
    4         private float score; 
     4        private double score; 
    55        private MatrixEntry previous; 
    66        private int xvalue; 
    … …  
    1515        } 
    1616 
    17         public float getScore() { 
     17        public double getScore() { 
    1818                return score; 
    1919        } 
    20         public void setScore(float score) { 
     20        public void setScore(double score) { 
    2121                this.score = score; 
    2222        } 

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

    r1559 r1568  
    33import java.io.Serializable; 
    44import java.util.ArrayList; 
     5import java.util.Random; 
    56 
    67public class NumberSequence implements Serializable { 
    … …  
    3334                System.out.println(); 
    3435        } 
     36         
     37        public NumberSequence shuffle(){ 
     38                NumberSequence result = new NumberSequence(sequence.length); 
     39                result.setSequence(this.sequence); 
     40                Random rgen = new Random(); 
     41                 
     42                for (int i=0; i<result.sequence.length; i++) { 
     43                    int randomPosition = rgen.nextInt(result.sequence.length); 
     44                    int temp = result.sequence[i]; 
     45                    result.sequence[i] = result.sequence[randomPosition]; 
     46                    result.sequence[randomPosition] = temp; 
     47                } 
     48                return result; 
     49                 
     50        } 
    3551 
    3652} 

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

    r1559 r1568  
    7171         * @return Cost of substitution of the character in str1 by the one in str2 
    7272         */ 
    73         private float similarity(int i, int j) {  
     73        private double similarity(int i, int j) {  
    7474                return submat.getDistance(input1[i - 1], input2[j - 1]); 
    7575        } 
    … …  
    101101                        // F(i,0) = max { F(i-1,0), F(i-1,j)-T  j=1,...,m 
    102102                         
    103                         float firstRowLeftScore = matrix[i-1][0].getScore(); 
     103                        double firstRowLeftScore = matrix[i-1][0].getScore(); 
    104104                        //for sequences of length 1 
    105                         float tempMax; 
     105                        double tempMax; 
    106106                        int maxRowIndex; 
    107107                        if(length2 == 1) { 
    … …  
    138138                                matrix[i][0].setXvalue(input1[i-1]); 
    139139                                matrix[i][0].setYvalue(-2); 
    140                                  
    141140                        } 
    142141                        else {  
    … …  
    147146                         
    148147                        for (int j = 1; j < length2; j++) { 
    149                                 float diagScore = matrix[i - 1][j - 1].getScore() + similarity(i, j); 
    150                                 float upScore = matrix[i][j - 1].getScore() + submat.getGapPenalty(); 
    151                                 float leftScore = matrix[i - 1][j].getScore() + submat.getGapPenalty(); 
     148                                double diagScore = matrix[i - 1][j - 1].getScore() + similarity(i, j); 
     149                                double upScore = matrix[i][j - 1].getScore() + submat.getGapPenalty(); 
     150                                double leftScore = matrix[i - 1][j].getScore() + submat.getGapPenalty(); 
    152151 
    153152                                matrix[i][j].setScore(Math.max(diagScore,Math.max(upScore, Math.max(leftScore,matrix[i][0].getScore())))); 
    … …  
    207206         * Get the alignment score between the two input strings. 
    208207         */ 
    209         public float getAlignmentScore() { 
     208        public double getAlignmentScore() { 
    210209                return matrix[length1+1][0].getScore(); 
    211210        } 
    … …  
    213212         
    214213         
    215          
    216         /** 
    217          * given the bottom right corner point trace back the top left conrner. at 
    218          * entry: i, j hold bottom right (end of Aligment coords) at return: hold 
    219          * top left (start of Alignment coords) 
    220          */ 
    221214        private int[] traceback(int i, int j) { 
    222215                 
    … …  
    225218        } 
    226219         
    227         public void traceback() { 
     220        public List<Match> traceback() { 
    228221                MatrixEntry tmp = matrix[length1+1][0]; 
    229222                String aligned1 = ""; 
    … …  
    266259                System.out.println(aligned1); 
    267260                System.out.println(aligned2); 
     261                return null; 
    268262        } 
    269263         

  • branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/substitution/DifferenceSubstitutionMatrix.java

    r1554 r1568  
    2929         * @see de.ugoe.cs.autoquest.plugin.alignment.SubstitutionMatrix#getDistance(int, int) 
    3030         */ 
    31         public float getDistance(int pos1, int pos2) { 
     31        public double getDistance(int pos1, int pos2) { 
    3232                return maxValue - (input1[pos1] - input2[pos2]); 
    3333        } 
    … …  
    4949 
    5050        @Override 
    51         public float getGapPenalty() { 
     51        public double getGapPenalty() { 
    5252                return -maxValue; 
    5353        } 

  • branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/substitution/NearbySubstitutionMatrix.java

    r1554 r1568  
    2929         * @see de.ugoe.cs.autoquest.plugin.alignment.SubstitutionMatrix#getDistance(int, int) 
    3030         */ 
    31         public float getDistance(int pos1, int pos2) { 
     31        public double getDistance(int pos1, int pos2) { 
    3232                int difference = Math.abs(input1[pos1]-input2[pos2]);  
    3333                if(difference < range) { 
    … …  
    4141 
    4242        @Override 
    43         public float getGapPenalty() { 
     43        public double getGapPenalty() { 
    4444                return -range-1; 
    4545        } 

  • branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/substitution/ObjectDistanceSubstitionMatrix.java

    r1559 r1568  
    2626        private TriangleMatrix matrix; 
    2727        private SymbolMap<ITaskInstance, ITask> uniqueTasks; 
    28         private float gapPenalty;  
    29         private float positiveThreshold; 
     28        private double gapPenalty;  
     29        private double positiveThreshold; 
    3030         
    3131        public ObjectDistanceSubstitionMatrix( 
    … …  
    4040 
    4141        @Override 
    42         public float getGapPenalty() { 
     42        public double getGapPenalty() { 
    4343                return gapPenalty; 
    4444        } 
    … …  
    4848                int index = 0; 
    4949                //TODO We need to determine this parameter before generating the matrix.. 
    50                 float meandistance = 18; 
     50                //float meandistance = 18; 
    5151                //TODO We need to determine this parameter before generating the matrix.. 
    5252                float maxDistance =34; 
    … …  
    5858                                eti1 = (IEventTaskInstance) obj1; 
    5959                        } 
     60                        //System.out.println(eti1.getTask().toString()); 
    6061                 
    6162                        for (Iterator<ITaskInstance> jt = uniqueTasks.getSymbols() 
    … …  
    121122 
    122123        @Override 
    123         public float getDistance(int taskId1, int taskId2) { 
     124        public double getDistance(int taskId1, int taskId2) { 
    124125                //System.out.println("Taskid1: " + taskId1 + " Taskid2: " + taskId2 + " Idmapping1: " + idmapping.get(taskId1) + " Idmapping2: " + idmapping.get(taskId2)); 
    125126                return matrix.get(idmapping.get(taskId1),idmapping.get(taskId2)); 

  • branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/substitution/SubstitutionMatrix.java

    r1554 r1568  
    1111         
    1212 
    13         public float getDistance(int pos1, int pos2); 
     13        public double getDistance(int pos1, int pos2); 
    1414 
    15         public float getGapPenalty(); 
     15        public double getGapPenalty(); 
    1616 
    1717        public void generate(); 

  • branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/substitution/TriangleMatrix.java

    r1558 r1568  
    33public class TriangleMatrix { 
    44         
    5         private float[] matrix; 
     5        private double[] matrix; 
    66        private int size; 
    77         
    88        public TriangleMatrix(int size) { 
    99                this.size = size; 
    10                 matrix = new float [size*(size+1)/2]; 
     10                matrix = new double [size*(size+1)/2]; 
    1111        } 
    1212         
    13         public float get(int first, int second) { 
     13        public double get(int first, int second) { 
    1414                int row = Math.min(first, second); 
    1515                int col = Math.max(first, second); 
    … …  
    1818        } 
    1919         
    20         public void set(int first, int second, float value) { 
     20        public void set(int first, int second, double value) { 
    2121                int row = Math.min(first, second); 
    2222                int col = Math.max(first, second); 

  • branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRuleAlignment.java

    r1559 r1568  
    3030import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.SmithWatermanRepeated; 
    3131import de.ugoe.cs.autoquest.tasktrees.alignment.substitution.ObjectDistanceSubstitionMatrix; 
     32import de.ugoe.cs.autoquest.tasktrees.alignment.substitution.TriangleMatrix; 
    3233import de.ugoe.cs.autoquest.tasktrees.taskequality.TaskEquality; 
    3334import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration; 
    … …  
    156157                // this is the real rule application. Loop while something is replaced. 
    157158                SymbolMap<ITaskInstance, ITask> uniqueTasks = harmonizeEventTaskInstancesModel(appData); 
     159 
    158160                ObjectDistanceSubstitionMatrix submat = new ObjectDistanceSubstitionMatrix( 
    159161                                uniqueTasks, 5); 
    160162                submat.generate(); 
    161163 
    162                 // good tests: 7/8 20/24 
     164                TriangleMatrix sequenceDistances = new TriangleMatrix(numberseqs.size()); 
     165 
    163166                for (int i = 0; i < numberseqs.size(); i++) { 
     167                        NumberSequence ns1 = numberseqs.get(i); 
     168                        //System.out.print("Sequence " + i + ": "); 
     169                        //ns1.printSequence(); 
    164170                        for (int j = 0; j < numberseqs.size(); j++) { 
     171                                NumberSequence ns2 = numberseqs.get(j); 
     172 
     173                                if (i != j) { 
     174                                        int smithWatermanThreshold = 10; 
     175 
     176                                        SmithWatermanRepeated twoSequences = new SmithWatermanRepeated( 
     177                                                        ns1.getSequence(), ns2.getSequence(), submat, 
     178                                                        smithWatermanThreshold); 
     179                                        SmithWatermanRepeated sameSequence1 = new SmithWatermanRepeated( 
     180                                                        ns1.getSequence(), ns1.getSequence(), submat, 
     181                                                        smithWatermanThreshold); 
     182                                        SmithWatermanRepeated sameSequence2 = new SmithWatermanRepeated( 
     183                                                        ns2.getSequence(), ns2.getSequence(), submat, 
     184                                                        smithWatermanThreshold); 
     185                                         
     186                                        SmithWatermanRepeated randomSequence = new SmithWatermanRepeated( 
     187                                                        ns1.shuffle().getSequence(),ns2.shuffle().getSequence(),submat,smithWatermanThreshold); 
     188                                        //randomSequence.printDPMatrix(); 
     189                                        //randomSequence.traceback(); 
     190                                         
     191                                        double score = twoSequences.getAlignmentScore(); 
     192                                        // Scores of the sequence beeing aligned to itself 
     193                                        double sSelf1 = sameSequence1.getAlignmentScore(); 
     194                                        double sSelf2 = sameSequence2.getAlignmentScore(); 
     195 
     196                                        double sRand = randomSequence.getAlignmentScore(); 
     197 
     198                                        double sMax = (sSelf1 + sSelf2) / 2; 
     199                                        double sEff = (score - sRand)/ (sMax - sRand); 
     200                                        double distance = -Math.log(sEff); 
    165201                                 
    166                                 NumberSequence ns1 = numberseqs.get(i); 
    167                                 NumberSequence ns2 = numberseqs.get(j); 
    168                                  
    169                                  
    170                                  
    171                                 SmithWatermanRepeated sw = new SmithWatermanRepeated( 
    172                                                 ns1.getSequence(), ns2.getSequence(), submat, 10); 
    173                                  
    174                                 if(sw.getAlignmentScore() > 0) 
    175                                 {    
    176                                         System.out.println("================================================="); 
    177                                         System.out.println("| Sequence " + String.format("%3d", i) +" Sequence " + String.format("%3d", j)  + "                     |"); 
    178                                         System.out.println("================================================="); 
    179                                         //System.out.print("Sequence " + i + ": "); 
    180                                         //ns1.printSequence(); 
    181                                         //System.out.print("Sequence " + j + ": "); 
    182                                         //ns2.printSequence(); 
    183                                         //System.out.println("Max Scrore: " + sw.getMaxScore()); 
    184                                         System.out.println("Alignment Score: " + sw.getAlignmentScore()); 
    185                                         //sw.printDPMatrix(); 
    186                                         sw.traceback(); 
    187                                         System.out.println(); 
    188                                         System.out.println(); 
    189                                 } 
    190                         } 
    191                 } 
    192  
     202                                        System.out.println("Score: " + score + " sRand: " + sRand + " sMax: " + sMax + " sEff: " + sEff + " distance: " + distance); 
     203                                         
     204                                        sequenceDistances.set(i,j,distance ); 
     205 
     206                                        if (score > 0) { 
     207                                                /* 
     208                                                 * System.out.println( 
     209                                                 * "================================================="); 
     210                                                 * System.out.println("| Sequence " + 
     211                                                 * String.format("%3d", i) +" Sequence " + 
     212                                                 * String.format("%3d", j) + "                     |"); 
     213                                                 * System.out.println( 
     214                                                 * "================================================="); 
     215                                                 * System.out.print("Sequence " + i + ": "); 
     216                                                 * ns1.printSequence(); System.out.print("Sequence " + j 
     217                                                 * + ": "); ns2.printSequence(); System.out.println(); 
     218                                                 * //System.out.println("Max Scrore: " + 
     219                                                 * sw.getMaxScore()); 
     220                                                 * System.out.println("Alignment Score: " + 
     221                                                 * sw.getAlignmentScore()); //sw.printDPMatrix(); 
     222                                                 * sw.traceback(); System.out.println(); 
     223                                                 * System.out.println(); 
     224                                                 */ 
     225                                        } 
     226                                } 
     227                        } 
     228                } 
     229                //System.out.println(sequenceDistances.toString()); 
     230                 
    193231                do { 
    194232                        System.out.println(); 
Note: See TracChangeset for help on using the changeset viewer.