Index: trunk/autoquest-plugin-alignment/.project
===================================================================
--- trunk/autoquest-plugin-alignment/.project (revision 1311)
+++ trunk/autoquest-plugin-alignment/.project (revision 1311)
@@ -0,0 +1,23 @@
+
+
+ autoquest-plugin-alignment
+
+
+
+
+
+ org.eclipse.jdt.core.javabuilder
+
+
+
+
+ org.eclipse.m2e.core.maven2Builder
+
+
+
+
+
+ org.eclipse.m2e.core.maven2Nature
+ org.eclipse.jdt.core.javanature
+
+
Index: trunk/autoquest-plugin-alignment/pom.xml
===================================================================
--- trunk/autoquest-plugin-alignment/pom.xml (revision 1311)
+++ trunk/autoquest-plugin-alignment/pom.xml (revision 1311)
@@ -0,0 +1,65 @@
+
+
+ de.ugoe.cs.autoquest
+ autoquest
+ 0.0.1-SNAPSHOT
+
+ 4.0.0
+ autoquest-plugin-alignment
+ autoquest-plugin-alignment
+
+
+ The Apache Software License, Version 2.0
+ http://www.apache.org/licenses/LICENSE-2.0.txt
+
+
+
+ ${autoquest-scm-trunk-dir}/autoquest-plugin-alignment
+
+
+
+ de.ugoe.cs
+ java-utils
+ 0.0.1-SNAPSHOT
+
+
+ de.ugoe.cs.autoquest
+ autoquest-plugin-core
+ ${project.parent.version}
+
+
+ de.ugoe.cs.autoquest
+ autoquest-core-events
+ ${project.parent.version}
+
+
+ de.ugoe.cs.autoquest
+ autoquest-core-usageprofiles
+ ${project.parent.version}
+
+
+ de.ugoe.cs.autoquest
+ autoquest-misc
+ ${project.parent.version}
+
+
+
+
+
+ org.apache.maven.plugins
+ maven-jar-plugin
+
+
+
+ true
+
+
+
+
+
+
+
Index: trunk/autoquest-plugin-alignment/src/main/java/de/ugoe/cs/autoquest/plugin/alignment/ALIGNMENTPlugin.java
===================================================================
--- trunk/autoquest-plugin-alignment/src/main/java/de/ugoe/cs/autoquest/plugin/alignment/ALIGNMENTPlugin.java (revision 1311)
+++ trunk/autoquest-plugin-alignment/src/main/java/de/ugoe/cs/autoquest/plugin/alignment/ALIGNMENTPlugin.java (revision 1311)
@@ -0,0 +1,60 @@
+// Copyright 2012 Georg-August-Universität Göttingen, Germany
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package de.ugoe.cs.autoquest.plugin.alignment;
+
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+
+import de.ugoe.cs.autoquest.plugin.AutoQUESTPlugin;
+
+/**
+ *
+ * Identifier class for the AutoQUEST Alignment plugin
+ *
+ *
+ * @author Ralph Krimmel
+ * @version 1.0
+ */
+public class ALIGNMENTPlugin implements AutoQUESTPlugin {
+
+ /**
+ *
+ * The command packages of this plug-in.
+ *
+ */
+ private final static String[] commandPackages = new String[] { "de.ugoe.cs.autoquest.plugin.alignment.commands" };
+
+ /*
+ * (non-Javadoc)
+ *
+ * @see de.ugoe.cs.autoquest.plugin.AutoQUESTPlugin#getTitle()
+ */
+ @Override
+ public String getTitle() {
+ return "Alignment-Plugin";
+ }
+
+ /*
+ * (non-Javadoc)
+ *
+ * @see de.ugoe.cs.autoquest.plugin.AutoQUESTPlugin#getCommandPackages()
+ */
+ @Override
+ public List getCommandPackages() {
+ return Collections.unmodifiableList(Arrays.asList(commandPackages));
+ }
+
+}
Index: trunk/autoquest-plugin-alignment/src/main/java/de/ugoe/cs/autoquest/plugin/alignment/Alignment.java
===================================================================
--- trunk/autoquest-plugin-alignment/src/main/java/de/ugoe/cs/autoquest/plugin/alignment/Alignment.java (revision 1311)
+++ trunk/autoquest-plugin-alignment/src/main/java/de/ugoe/cs/autoquest/plugin/alignment/Alignment.java (revision 1311)
@@ -0,0 +1,8 @@
+package de.ugoe.cs.autoquest.plugin.alignment;
+
+import java.util.List;
+
+public interface Alignment {
+ public List getMatches();
+
+}
Index: trunk/autoquest-plugin-alignment/src/main/java/de/ugoe/cs/autoquest/plugin/alignment/DifferenceSubstitutionMatrix.java
===================================================================
--- trunk/autoquest-plugin-alignment/src/main/java/de/ugoe/cs/autoquest/plugin/alignment/DifferenceSubstitutionMatrix.java (revision 1311)
+++ trunk/autoquest-plugin-alignment/src/main/java/de/ugoe/cs/autoquest/plugin/alignment/DifferenceSubstitutionMatrix.java (revision 1311)
@@ -0,0 +1,54 @@
+/**
+ *
+ */
+package de.ugoe.cs.autoquest.plugin.alignment;
+
+/**
+ * @author Ralph Krimmel
+ *
+ */
+public class DifferenceSubstitutionMatrix implements SubstitutionMatrix {
+
+ private int[] input1;
+ private int[] input2;
+ private int maxValue;
+
+ public DifferenceSubstitutionMatrix(int[] input1,int[] input2) {
+ this.input1 = input1;
+ this.input2 = input2;
+ this.maxValue = getMaxValue();
+ }
+
+ /* (non-Javadoc)
+ * @see de.ugoe.cs.autoquest.plugin.alignment.SubstitutionMatrix#getDistance(int, int)
+ */
+ public double getDistance(int pos1, int pos2) {
+ return maxValue - (input1[pos1] - input2[pos2]);
+ }
+
+ private int getMaxValue() {
+ int max = input1[0];
+ for (int i=0; i < input1.length; i++) {
+ if(input1[i] > max) {
+ max = input1[i];
+ }
+ }
+ for (int j=0; j < input2.length; j++) {
+ if(input2[j] > max) {
+ max = input2[j];
+ }
+ }
+ return max;
+ }
+
+ @Override
+ public double getGapPenalty() {
+ return -maxValue;
+ }
+
+ @Override
+ public String info() {
+ return "Max Value: " + maxValue;
+ }
+
+}
Index: trunk/autoquest-plugin-alignment/src/main/java/de/ugoe/cs/autoquest/plugin/alignment/Match.java
===================================================================
--- trunk/autoquest-plugin-alignment/src/main/java/de/ugoe/cs/autoquest/plugin/alignment/Match.java (revision 1311)
+++ trunk/autoquest-plugin-alignment/src/main/java/de/ugoe/cs/autoquest/plugin/alignment/Match.java (revision 1311)
@@ -0,0 +1,9 @@
+package de.ugoe.cs.autoquest.plugin.alignment;
+
+public class Match {
+
+
+ private float score;
+ private int start;
+ private int end;
+}
Index: trunk/autoquest-plugin-alignment/src/main/java/de/ugoe/cs/autoquest/plugin/alignment/NearbySubstitutionMatrix.java
===================================================================
--- trunk/autoquest-plugin-alignment/src/main/java/de/ugoe/cs/autoquest/plugin/alignment/NearbySubstitutionMatrix.java (revision 1311)
+++ trunk/autoquest-plugin-alignment/src/main/java/de/ugoe/cs/autoquest/plugin/alignment/NearbySubstitutionMatrix.java (revision 1311)
@@ -0,0 +1,46 @@
+/**
+ *
+ */
+package de.ugoe.cs.autoquest.plugin.alignment;
+
+/**
+ * @author Ralph Krimmel
+ *
+ */
+public class NearbySubstitutionMatrix implements SubstitutionMatrix {
+
+ private int[] input1;
+ private int[] input2;
+ private int range;
+
+ public NearbySubstitutionMatrix(int[] input1,int[] input2, int range) {
+ this.input1 = input1;
+ this.input2 = input2;
+ this.range = range;
+ }
+
+ /* (non-Javadoc)
+ * @see de.ugoe.cs.autoquest.plugin.alignment.SubstitutionMatrix#getDistance(int, int)
+ */
+ public double getDistance(int pos1, int pos2) {
+ int difference = Math.abs(input1[pos1]-input2[pos2]);
+ if(difference < range) {
+ return range-difference;
+ }
+ else {
+ return -range;
+ }
+ }
+
+
+ @Override
+ public double getGapPenalty() {
+ return -range-1;
+ }
+
+ @Override
+ public String info() {
+ return "Range: " + range;
+ }
+
+}
Index: trunk/autoquest-plugin-alignment/src/main/java/de/ugoe/cs/autoquest/plugin/alignment/SmithWaterman.java
===================================================================
--- trunk/autoquest-plugin-alignment/src/main/java/de/ugoe/cs/autoquest/plugin/alignment/SmithWaterman.java (revision 1311)
+++ trunk/autoquest-plugin-alignment/src/main/java/de/ugoe/cs/autoquest/plugin/alignment/SmithWaterman.java (revision 1311)
@@ -0,0 +1,329 @@
+package de.ugoe.cs.autoquest.plugin.alignment;
+
+import java.util.ArrayList;
+import java.util.List;
+
+public class SmithWaterman implements Alignment {
+
+ /**
+ * 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 double[][] score;
+
+ /**
+ * Score threshold
+ */
+ private int scoreThreshold;;
+
+ /**
+ * The similarity function constants.
+ */
+ // static final int MATCH_SCORE = 10;
+ // static final int MISMATCH_SCORE = -8;
+ // static final int INDEL_SCORE = -9;
+
+ /**
+ * Constants of directions. Multiple directions are stored by bits. The zero
+ * direction is the starting point.
+ */
+ static final int DR_LEFT = 1; // 0001
+ static final int DR_UP = 2; // 0010
+ static final int DR_DIAG = 4; // 0100
+ static final int DR_ZERO = 8; // 1000
+
+ /**
+ * The directions pointing to the cells that give the maximum score at the
+ * current cell. The first index is the column index. The second index is
+ * the row index.
+ */
+ private int[][] prevCells;
+
+ /**
+ * Substitution matrix to calculate scores
+ */
+ private SubstitutionMatrix submat;
+
+ public SmithWaterman(int[] input1, int[] input2, SubstitutionMatrix submat) {
+ 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.info());
+ scoreThreshold = 20;
+ score = new double[length1 + 1][length2 + 1];
+ prevCells = new int[length1 + 1][length2 + 1];
+
+ buildMatrix();
+ }
+
+ /**
+ * 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) {
+ if (i == 0 || j == 0) {
+ // it's a gap (indel)
+ return submat.getGapPenalty();
+ }
+ // System.out.println("Diag letters: " + input1[i-1] + " " +
+ // input2[j-1]);
+ // return (input1[i - 1] == input2[j - 1]) ? MATCH_SCORE :
+ // MISMATCH_SCORE;
+ return submat.getDistance(i - 1, j - 1);
+ }
+
+ /**
+ * Build the score matrix using dynamic programming. Note: The indel scores
+ * must be negative. Otherwise, the part handling the first row and column
+ * has to be modified.
+ */
+ private void buildMatrix() {
+ if (submat.getGapPenalty() >= 0) {
+ throw new Error("Indel score must be negative");
+ }
+
+ int i; // length of prefix substring of str1
+ int j; // length of prefix substring of str2
+
+ // base case
+ score[0][0] = 0;
+ prevCells[0][0] = DR_ZERO; // starting point
+
+ // the first row
+ for (i = 1; i <= length1; i++) {
+ score[i][0] = 0;
+ prevCells[i][0] = DR_ZERO;
+ }
+
+ // the first column
+ for (j = 1; j <= length2; j++) {
+ score[0][j] = 0;
+ prevCells[0][j] = DR_ZERO;
+ }
+
+ // the rest of the matrix
+ for (i = 1; i <= length1; i++) {
+ for (j = 1; j <= length2; j++) {
+ double diagScore = score[i - 1][j - 1] + similarity(i, j);
+ double upScore = score[i][j - 1] + similarity(0, j);
+ double leftScore = score[i - 1][j] + similarity(i, 0);
+
+ score[i][j] = Math.max(diagScore,
+ Math.max(upScore, Math.max(leftScore, 0)));
+ prevCells[i][j] = 0;
+
+ // find the directions that give the maximum scores.
+ // the bitwise OR operator is used to record multiple
+ // directions.
+ if (diagScore == score[i][j]) {
+ prevCells[i][j] |= DR_DIAG;
+ }
+ if (leftScore == score[i][j]) {
+ prevCells[i][j] |= DR_LEFT;
+ }
+ if (upScore == score[i][j]) {
+ prevCells[i][j] |= DR_UP;
+ }
+ if (0 == score[i][j]) {
+ prevCells[i][j] |= DR_ZERO;
+ }
+ }
+ }
+ }
+
+ /**
+ * Get the maximum value in the score matrix.
+ */
+ private 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 (score[i][j] > maxScore) {
+ maxScore = score[i][j];
+ }
+ }
+ }
+
+ return maxScore;
+ }
+
+ /**
+ * Get the alignment score between the two input strings.
+ */
+ public double getAlignmentScore() {
+ return getMaxScore();
+ }
+
+ /**
+ * TODO: Iterative Version!!! Output the local alignments ending in the (i,
+ * j) cell. aligned1 and aligned2 are suffixes of final aligned strings
+ * found in backtracking before calling this function. Note: the strings are
+ * replicated at each recursive call. Use buffers or stacks to improve
+ * efficiency.
+ */
+ private void printAlignments(int i, int j, String aligned1, String aligned2) {
+ // we've reached the starting point, so print the alignments
+
+ if ((prevCells[i][j] & DR_ZERO) > 0) {
+ System.out.println(aligned1);
+ System.out.println(aligned2);
+ System.out.println();
+
+ // Note: we could check other directions for longer alignments
+ // with the same score. we don't do it here.
+ return;
+ }
+
+ // find out which directions to backtrack
+ if ((prevCells[i][j] & DR_LEFT) > 0) {
+ printAlignments(i - 1, j, input1[i - 1] + aligned1, "_ " + aligned2);
+ }
+ if ((prevCells[i][j] & DR_UP) > 0) {
+ printAlignments(i, j - 1, "_ " + aligned1, input2[j - 1] + aligned2);
+ }
+ if ((prevCells[i][j] & DR_DIAG) > 0) {
+ printAlignments(i - 1, j - 1, input1[i - 1] + " " + aligned1,
+ input2[j - 1] + " " + aligned2);
+ }
+ }
+
+ /**
+ * given the bottom right corner point trace back the top left conrner. at
+ * entry: i, j hold bottom right (end of Aligment coords) at return: hold
+ * top left (start of Alignment coords)
+ */
+ private int[] traceback(int i, int j) {
+
+ // find out which directions to backtrack
+ while (true) {
+ if ((prevCells[i][j] & DR_LEFT) > 0) {
+ if (score[i - 1][j] > 0)
+ i--;
+ else
+ break;
+ }
+ if ((prevCells[i][j] & DR_UP) > 0) {
+ // return traceback(i, j-1);
+ if (score[i][j - 1] > 0)
+ j--;
+ else
+ break;
+ }
+ if ((prevCells[i][j] & DR_DIAG) > 0) {
+ // return traceback(i-1, j-1);
+ if (score[i - 1][j - 1] > 0) {
+ i--;
+ j--;
+ } else
+ break;
+ }
+ }
+ int[] m = { i, j };
+ return m;
+ }
+
+ /**
+ * Output the local alignments with the maximum score.
+ */
+ public void printAlignments() {
+ // find the cell with the maximum score
+ double maxScore = getMaxScore();
+
+ /*
+ * for (int i = 0; i < matches.length; i++) {
+ * System.out.println("Match #" + i + ":" + matches.get(i)); }
+ */
+
+ // skip the first row and column
+ for (int i = 1; i <= length1; i++) {
+ for (int j = 1; j <= length2; j++) {
+ if (score[i][j] == maxScore) {
+ printAlignments(i, j, "", "");
+ }
+ }
+ }
+ // Note: empty alignments are not printed.
+ }
+
+ /**
+ * print the dynmaic programming matrix
+ */
+ public void printDPMatrix() {
+ System.out.print(" ");
+ for (int j = 1; j <= length2; j++)
+ System.out.print(" " + input2[j - 1]);
+ System.out.println();
+ for (int i = 0; i <= length1; i++) {
+ if (i > 0)
+ System.out.print(input1[i - 1] + " ");
+ else
+ System.out.print(" ");
+ for (int j = 0; j <= length2; j++) {
+ System.out.print(score[i][j] + " ");
+ }
+ System.out.println();
+ }
+ }
+
+ /**
+ * Return a set of Matches identified in Dynamic programming matrix. A match
+ * is a pair of subsequences whose score is higher than the preset
+ * scoreThreshold
+ **/
+ public List getMatches() {
+ ArrayList matchList = new ArrayList();
+ int fA = 0, fB = 0;
+ // skip the first row and column, find the next maxScore after
+ // prevmaxScore
+ for (int i = 1; i <= length1; i++) {
+ for (int j = 1; j <= length2; j++) {
+ if (score[i][j] > scoreThreshold
+ && score[i][j] > score[i - 1][j - 1]
+ && score[i][j] > score[i - 1][j]
+ && score[i][j] > score[i][j - 1]) {
+ if (i == length1 || j == length2
+ || score[i][j] > score[i + 1][j + 1]) {
+ // should be lesser than prev maxScore
+ fA = i;
+ fB = j;
+ int[] f = traceback(fA, fB); // sets the x, y to
+ // startAlignment
+ // coordinates
+ System.out.println(f[0] + " " + i + " " + f[1] + " "
+ + j + " " + score[i][j]);
+ // TODO Add matches to matchList
+ }
+ }
+ }
+ }
+ return matchList;
+ }
+
+}
Index: trunk/autoquest-plugin-alignment/src/main/java/de/ugoe/cs/autoquest/plugin/alignment/SubstitutionMatrix.java
===================================================================
--- trunk/autoquest-plugin-alignment/src/main/java/de/ugoe/cs/autoquest/plugin/alignment/SubstitutionMatrix.java (revision 1311)
+++ trunk/autoquest-plugin-alignment/src/main/java/de/ugoe/cs/autoquest/plugin/alignment/SubstitutionMatrix.java (revision 1311)
@@ -0,0 +1,12 @@
+package de.ugoe.cs.autoquest.plugin.alignment;
+
+public interface SubstitutionMatrix {
+
+ public String info();
+
+ public double getDistance(int pos1, int pos2);
+
+ public double getGapPenalty();
+
+
+}
Index: trunk/autoquest-plugin-alignment/src/main/java/de/ugoe/cs/autoquest/plugin/alignment/commands/CMDbinaryAlignment.java
===================================================================
--- trunk/autoquest-plugin-alignment/src/main/java/de/ugoe/cs/autoquest/plugin/alignment/commands/CMDbinaryAlignment.java (revision 1311)
+++ trunk/autoquest-plugin-alignment/src/main/java/de/ugoe/cs/autoquest/plugin/alignment/commands/CMDbinaryAlignment.java (revision 1311)
@@ -0,0 +1,98 @@
+// Copyright 2012 Georg-August-Universität Göttingen, Germany
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package de.ugoe.cs.autoquest.plugin.alignment.commands;
+
+import java.io.File;
+import java.io.FilenameFilter;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.logging.Level;
+
+import de.ugoe.cs.autoquest.CommandHelpers;
+import de.ugoe.cs.autoquest.eventcore.Event;
+import de.ugoe.cs.autoquest.plugin.alignment.NearbySubstitutionMatrix;
+import de.ugoe.cs.autoquest.plugin.alignment.SmithWaterman;
+import de.ugoe.cs.autoquest.plugin.alignment.DifferenceSubstitutionMatrix;
+import de.ugoe.cs.autoquest.plugin.alignment.seqgen.RandomSequenceGenerator;
+import de.ugoe.cs.util.console.Command;
+import de.ugoe.cs.util.console.Console;
+import de.ugoe.cs.util.console.GlobalDataContainer;
+
+/**
+ *
+ * Command to generate a binary alignment of two sequences
+ *
+ *
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+public class CMDbinaryAlignment implements Command {
+
+ /*
+ * (non-Javadoc)
+ *
+ * @see de.ugoe.cs.util.console.Command#run(java.util.List)
+ */
+ @Override
+ public void run(List