Changeset 1585

Timestamp:

06/29/14 11:11:30 (10 years ago)

Author:

rkrimmel

Message:

Multiple Alignment first version

Location:

branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees

Files:

• alignment/algorithms/SmithWatermanRepeated.java (modified) (3 diffs)
• alignment/matrix/BinaryAlignmentStorage.java (modified) (1 diff)
• alignment/matrix/ObjectDistanceSubstitionMatrix.java (modified) (1 diff)
• alignment/pal/tree/FengDoolittleNode.java (modified) (3 diffs)
• alignment/pal/tree/Node.java (modified) (1 diff)
• alignment/pal/tree/UPGMAAligningTree.java (modified) (8 diffs)
• temporalrelation/SequenceForTaskDetectionRuleAlignment.java (modified) (2 diffs)

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

@@ -2 +2 @@
 
 import java.util.ArrayList;
-import java.util.List;
 import java.util.logging.Level;
 
@@ -33 +32 @@
 
 
-        private List<NumberSequence> alignment;
+        private ArrayList<NumberSequence> alignment;
         
         private float scoreThreshold;
@@ -329 +328 @@
 
 
-        public List<NumberSequence> getAlignment() {
+        public ArrayList<NumberSequence> getAlignment() {
                 return alignment;
         }
 
-        public void setAlignment(List<NumberSequence> alignment) {
+        public void setAlignment(ArrayList<NumberSequence> alignment) {
                 this.alignment = alignment;
         }

branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/matrix/BinaryAlignmentStorage.java

@@ -9 +9 @@
     UPGMAMatrix sequenceDistances;
    
-    public BinaryAlignmentStorage(int size) {
-        alignments = new SmithWatermanRepeated[size][size];
-        sequenceDistances = new UPGMAMatrix(size);
+    public BinaryAlignmentStorage(int sizex, int sizey) {
+        alignments = new SmithWatermanRepeated[sizex+1][sizey+1];
+        sequenceDistances = new UPGMAMatrix(Math.max(sizex,sizey));
         sequenceDistances.initialize(Double.POSITIVE_INFINITY);
     }

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

@@ -29 +29 @@
                 idmapping = new HashMap<Integer, Integer>();
                 matrix = new TriangleMatrix(uniqueTasks.size()+1);
-                gapPenalty = -5;
+                gapPenalty = -3;
                 
         }

branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/FengDoolittleNode.java

@@ -344 +344 @@
          * @param n2 number of second child
          */
-        public void joinChildren( int n1, int n2) {
+        public Node joinChildren( int n1, int n2) {
 
                 if (n1 == n2) {
@@ -376 +376 @@
                 //System.out.println("Merging " + child1.getIdentifier() + " with " + child2.getIdentifier());
                 
-                if(newNode instanceof FengDoolittleNode) {
-                        newNode.setSequences(((FengDoolittleNode) newNode).alignSequences());
-                }
-                
+                return newNode;
         }
         
@@ -397 +394 @@
 
 
-        private ArrayList<NumberSequence> alignSequences() {
-                ArrayList<NumberSequence> alignment = new ArrayList<NumberSequence>();
-                if(this.getChildCount()<3) {
-                        
-                        Node node1 = getChild(0);
-                        Node node2 = getChild(1);
-                        
-                        int seqCount1 = node1.getSequences().size();
-                        int seqCount2 = node2.getSequences().size();
-                        
-                        //Align 2 sequences
-                        if(seqCount1 == 1 && seqCount2 == 1) {
-                        }
-                        //Align a sequence to a group
-                        else if( seqCount1 > 1 && seqCount2 == 1) {
-                        
-                        }
-                        //Align a sequence to a group
-                        else if(seqCount1 == 1 && seqCount2 > 1) {
-                                
-                        }
-                        //Align 2 groups
-                        else if((seqCount1 > 1) && (seqCount2 > 1)){
-                                        
-                        }
-                        else {
-                                Console.traceln(Level.INFO,"No sequences to align while merging two nodes.");
-                        }
-                }
-                else {
-                        Console.traceln(Level.WARNING,"More than 2 children! This should never happen, it's a binary tree.");
-                }
-                return alignment;
-        }
-
         public void setSequences(ArrayList<NumberSequence> alignSequences) {
                 this.sequences = alignSequences;
         }
         
+        
+        
 }

branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/Node.java

@@ -134 +134 @@
         ArrayList<NumberSequence> getSequences();
         
-        void joinChildren( int n1, int n2);
+        Node joinChildren( int n1, int n2);
 
         void addSequence(NumberSequence numberSequence);

branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/UPGMAAligningTree.java

@@ -15 +15 @@
 
 import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.logging.Level;
 
 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.ObjectDistanceSubstitionMatrix;
 import de.ugoe.cs.autoquest.tasktrees.alignment.matrix.UPGMAMatrix;
 import de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc.Identifier;
+import de.ugoe.cs.util.console.Console;
 
 
@@ -42 +47 @@
          * @param m distance matrix
          */
-        public UPGMAAligningTree(ArrayList<NumberSequence> numberseqs, BinaryAlignmentStorage alignments)
+        public UPGMAAligningTree(ArrayList<NumberSequence> numberseqs, BinaryAlignmentStorage alignments, ObjectDistanceSubstitionMatrix submat)
         {
                 if (alignments.getDistanceMatrix().size() < 2)
@@ -51 +56 @@
                 this.numberseqs = numberseqs;
                 this.alignments = alignments;
+                this.submat = submat;
                 init(alignments.getDistanceMatrix());
 
@@ -76 +82 @@
         private ArrayList<NumberSequence> numberseqs;
         private BinaryAlignmentStorage alignments;
+        private ObjectDistanceSubstitionMatrix submat;
         private int numClusters;
         private int besti, abi;
@@ -107 +114 @@
                         Node tmp = NodeFactory.createNode();
                         tmp.setIdentifier(new Identifier(Integer.toString(i)));
+                        tmp.setNumber(i);
                         tmp.addSequence(numberseqs.get(i));
                         getRoot().addChild(tmp);
@@ -181 +189 @@
                 
                 // Index besti now represent the new cluster
-                getRoot().joinChildren(besti, bestj);
+                Node newNode = getRoot().joinChildren(besti, bestj);
+                
+                if(newNode instanceof FengDoolittleNode) {
+                        newNode.setSequences(alignSequences(newNode));
+                }
                 
                 // Update alias
@@ -190 +202 @@
                 
                 numClusters--;
+        }
+        
+        
+        public ArrayList<NumberSequence> alignSequences(Node parent) {
+                ArrayList<NumberSequence> alignment = new ArrayList<NumberSequence>();
+                if(parent.getChildCount()<3) {
+                        
+                        Node node1 = parent.getChild(0);
+                        Node node2 = parent.getChild(1);
+                        
+                        int seqCount1 = node1.getSequences().size();
+                        int seqCount2 = node2.getSequences().size();
+                        Console.traceln(Level.INFO,"Merging node " + node1.getIdentifier() + " with " + node2.getIdentifier());
+                        //Console.println("SeqCount1: " + seqCount1 + " seqCount2 " + seqCount2);
+                        //Align 2 sequences
+                        if(seqCount1 == 1 && seqCount2 == 1) {
+                                alignment = (alignments.get(node1.getNumber(), node2.getNumber())).getAlignment();
+                        }
+                        //Align a sequence to a group
+                        else if( seqCount1 > 1 && seqCount2 == 1) {
+                                alignment.addAll(node1.getSequences());
+                                
+                                BinaryAlignmentStorage tempStorage = new BinaryAlignmentStorage(seqCount1,seqCount2);
+                                double maxScore = 0.0;
+                                int maxIndex = 0;
+                                for(int i=0;i<seqCount1;i++) {
+                                        tempStorage.set(i, 1, new SmithWatermanRepeated(node1.getSequence(i).getSequence(), node2.getSequence(0).getSequence() , submat, 5));
+                                        if(maxScore < tempStorage.get(i, 1).getAlignmentScore()) {
+                                                maxScore = tempStorage.get(i, 1).getAlignmentScore();
+                                                maxIndex = i;
+                                        }
+                                }
+                                alignment.add(tempStorage.get(maxIndex, 1).getAlignment().get(1));
+                        }
+                        //Align a sequence to a group
+                        else if(seqCount1 == 1 && seqCount2 > 1) {
+                                alignment.addAll(node2.getSequences());
+                                BinaryAlignmentStorage tempStorage = new BinaryAlignmentStorage(seqCount1,seqCount2);
+                                double maxScore = 0.0;
+                                int maxIndex = 0;
+                                for(int i=0;i<seqCount2;i++) {
+                                        tempStorage.set(1, i, new SmithWatermanRepeated(node2.getSequence(i).getSequence(), node1.getSequence(0).getSequence() , submat, 5));
+                                        if(maxScore < tempStorage.get(1, i).getAlignmentScore()) {
+                                                maxScore = tempStorage.get(1, i).getAlignmentScore();
+                                                maxIndex = i;
+                                        }
+                                }
+                                alignment.add(tempStorage.get(1,maxIndex).getAlignment().get(1));
+                        }
+                        //Align 2 groups
+                        else if((seqCount1 > 1) && (seqCount2 > 1)){
+                                        BinaryAlignmentStorage tempStorage1 = new BinaryAlignmentStorage(seqCount2,1);
+                                        BinaryAlignmentStorage tempStorage2 = new BinaryAlignmentStorage(seqCount1,1);
+                                        double maxScore1 = 0.0;
+                                        double maxScore2 = 0.0;
+                                        int maxIndex1 = 0;
+                                        int maxIndex2 = 0;
+                                        for(int i=0;i<seqCount1;i++) {
+                                                for(int j=0;j<seqCount2;j++) {
+                                                        tempStorage1.set(j, 0, new SmithWatermanRepeated(node1.getSequence(i).getSequence(), node2.getSequence(j).getSequence() , submat, 5));
+                                                        if(maxScore1 < tempStorage1.get(j, 0).getAlignmentScore()) {
+                                                                maxScore1 = tempStorage1.get(j, 0).getAlignmentScore();
+                                                                maxIndex1 = j;
+                                                        }
+                                                }
+                                                alignment.add(tempStorage1.get(maxIndex1,0).getAlignment().get(0));
+                                        }
+                                        for(int i=0; i<seqCount2;i++) {
+                                                for (int j=0;j<seqCount1;j++) {
+                                                        tempStorage2.set(j, 0, new SmithWatermanRepeated(node2.getSequence(i).getSequence(),node1.getSequence(j).getSequence(),submat,5));
+                                                        if(maxScore2 < tempStorage2.get(j, 0).getAlignmentScore()) {
+                                                                maxScore2 = tempStorage2.get(j, 0).getAlignmentScore();
+                                                                maxIndex2 = j;
+                                                        }
+                                                }
+                                                alignment.add(tempStorage2.get(maxIndex2,0).getAlignment().get(0));
+                                        }
+                                        
+                        }
+                        else {
+                                Console.traceln(Level.WARNING,"No sequences to align while merging " + node1.getIdentifier() + " with " + node2.getIdentifier());
+                        }
+                }
+                else {
+                        Console.traceln(Level.WARNING,"More than 2 children! This should never happen, it's a binary tree.");
+                }
+                return alignment;
         }
 
@@ -217 +316 @@
         }
 }
+
+

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

@@ -159 +159 @@
 
         
-                BinaryAlignmentStorage alignments = new BinaryAlignmentStorage(numberseqs.size());
+                BinaryAlignmentStorage alignments = new BinaryAlignmentStorage(numberseqs.size(),numberseqs.size());
 
 
@@ -207 +207 @@
                 }
                 //System.out.println(sequenceDistances.toString());
-                UPGMAAligningTree guidetree = new UPGMAAligningTree(numberseqs, alignments);
-                
+                UPGMAAligningTree guidetree = new UPGMAAligningTree(numberseqs, alignments,submat);
+
+                for (Iterator<NumberSequence> it =  guidetree.getRoot().getChild(0).getSequences().iterator(); it.hasNext();) {
+                        NumberSequence tmp  = it.next();
+                        tmp.printSequence();
+                }
         
                 /*