Index: anches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/FengDoolittle.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/FengDoolittle.java (revision 1578) +++ (revision ) @@ -1,18 +1,0 @@ -package de.ugoe.cs.autoquest.tasktrees.alignment.algorithms; - -import de.ugoe.cs.autoquest.tasktrees.alignment.matrix.TriangleMatrix; - -public class FengDoolittle { - - private TriangleMatrix scoreDistance; - - - - public FengDoolittle() { - - - - - } - -} Index: anches/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 1578) +++ (revision ) @@ -1,9 +1,0 @@ -package de.ugoe.cs.autoquest.tasktrees.alignment.algorithms; - -public class Match { - - - private float score; - private int start; - private int end; -} Index: anches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/SmithWaterman.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/SmithWaterman.java (revision 1578) +++ (revision ) @@ -1,333 +1,0 @@ -package de.ugoe.cs.autoquest.tasktrees.alignment.algorithms; - -import java.util.ArrayList; -import java.util.List; - -import de.ugoe.cs.autoquest.tasktrees.alignment.matrix.SubstitutionMatrix; - -public class SmithWaterman { - - /** - * 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.getClass().getCanonicalName()); - 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 - 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.getScore(input1[i - 1], input2[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. - */ - public 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, "", ""); - } - } - } - } - - /** - * print the dynmaic programming matrix - */ - public void printDPMatrix() { - System.out.print(" "); - for (int j = 1; j <= length2; j++) - System.out.format("%5d", input2[j - 1]); - System.out.println(); - for (int i = 0; i <= length1; i++) { - if (i > 0) - System.out.format("%5d ",input1[i - 1]); - else{ - System.out.print(" "); - } - for (int j = 0; j <= length2; j++) { - System.out.format("%4.1f ",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: anches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/misc/Attribute.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/misc/Attribute.java (revision 1578) +++ (revision ) @@ -1,82 +1,0 @@ -// Attribute.java -// -// (c) 1999-2001 PAL Development Core Team -// -// This package may be distributed under the -// terms of the Lesser GNU General Public License (LGPL) - -package de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc; - - - -/** - * An immutable attribute has a name and value. - * A convenience constructor for conversion from - * string to types Boolean, Integer, Double, Float is available. - * - * @version $Id: Attribute.java,v 1.1 2001/11/21 22:17:07 alexi Exp $ - * - * @author Alexei Drummond - */ - - -public class Attribute { - - public static final String STRING = "string"; - public static final String INTEGER = "integer"; - public static final String BOOLEAN = "boolean"; - public static final String DOUBLE = "double"; - public static final String FLOAT = "float"; - - /** the name of this attribute */ - private String name = null; - - /** the value of this attribute */ - private Object value = null; - - /** - * @param name the name of the attribute. - * @param val the value as a string - * @param type a string description of the type the value is. One of 'boolean', - * 'integer', 'double', 'float', 'string' - */ - public Attribute(String name, String val, String type) { - - this.name = name; - - if (type == null) { - try { - value = new Integer(val); - } catch (NumberFormatException nfe1) { - try { - value = new Double(val); - } catch (NumberFormatException nfe2) { - value = val; - } - } - } else if (type.equals(BOOLEAN)) { - value = new Boolean(val); - } else if (type.equals(INTEGER)) { - value = new Integer(val); - } else if (type.equals(DOUBLE)) { - value = new Double(val); - } else if (type.equals(FLOAT)) { - value = new Float(val); - } - value = val; - } - - public Attribute(String name, Object value) { - this.name = name; - this.value = value; - } - - public String getName() { - return name; - } - - public Object getValue() { - return value; - } -} - Index: anches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/misc/BranchLimits.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/misc/BranchLimits.java (revision 1578) +++ (revision ) @@ -1,39 +1,0 @@ -// BranchLimits.java -// -// (c) 1999-2001 PAL Development Core Team -// -// This package may be distributed under the -// terms of the Lesser GNU General Public License (LGPL) - - -package de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc; - - -/** - * limits for branch lengths - * - * @version $Id: BranchLimits.java,v 1.9 2001/09/09 22:15:16 alexi Exp $ - * - * @author Korbinian Strimmer - */ -public interface BranchLimits -{ - // - // Public stuff - // - - /** minimum branch length */ - double MINARC = 1.0e-9; - - /** maximum branch length */ - double MAXARC = 100.0; - - /** default branch length */ - double DEFAULT_LENGTH = 0.04; - - /** maximum tolerated error when determining branch lengths */ - double ABSTOL = 5.0e-07; - - /** desired fractional digits when determining branch lengths */ - int FRACDIGITS = 6; -} Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/misc/Identifier.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/misc/Identifier.java (revision 1578) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/misc/Identifier.java (revision 1579) @@ -8,5 +8,4 @@ package de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc; -import java.io.Serializable; import de.ugoe.cs.autoquest.tasktrees.alignment.pal.util.Comparable; Index: anches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/misc/LabelMapping.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/misc/LabelMapping.java (revision 1578) +++ (revision ) @@ -1,61 +1,0 @@ -// LableMapping.java -// -// (c) 1999-2001 PAL Development Core Team -// -// This package may be distributed under the -// terms of the Lesser GNU General Public License (LGPL) - -package de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc; - -/** - * Title: LabelMapping - * Description: Allows for the substitution of one label for another - * @author Matthew Goode - * @version 1.0 - */ -import java.util.*; -public class LabelMapping implements java.io.Serializable { - Hashtable mappings_ = new Hashtable(); - public LabelMapping() { } - - public void addMapping(String id, String label) { - mappings_.put(id,label); - } - public void addMapping(Identifier id, String label) { - if(id!=null&&id.getName()!=null) { - mappings_.put(id.getName(),label); - } - } - /** - * @param names Names - * @param colours associated colours - * @note assumes parallel arrays - */ - public void addMappings(String[] ids, String[] labels) { - for(int i = 0 ; i < ids.length ; i++) { - mappings_.put(ids[i],labels[i]); - } - } - - public String getLabel(String id, String defaultLabel) { - if(id==null||!mappings_.containsKey(id)) { - return defaultLabel; - } - return mappings_.get(id).toString(); - } - public String getLabel(Identifier id, String defaultLabel) { - if(id==null) { - return defaultLabel; - } - return getLabel(id.getName(),defaultLabel); - } - public String getLabel(Identifier id) { - return getLabel(id.getName(),id.getName()); - } - public Identifier getLabelIdentifier(Identifier id) { - if(id==null) { - return null; - } - return new Identifier(getLabel(id.getName(),id.getName())); - } -} Index: anches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/misc/Utils.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/misc/Utils.java (revision 1578) +++ (revision ) @@ -1,113 +1,0 @@ -// Utils.java -// -// (c) 1999-2001 PAL Development Core Team -// -// This package may be distributed under the -// terms of the Lesser GNU General Public License (LGPL) - -package de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc; - - - -/** - * Provides some miscellaneous methods. - * - * @version $Id: Utils.java,v 1.9 2001/11/20 19:58:45 alexi Exp $ - * - * @author Matthew Goode - */ -public class Utils { - - /** Clones an array of doubles - * @return null if input is null, otherwise return complete copy. - */ - public static final double[] getCopy(double[] array) { - - if(array == null) { - return null; - } - double[] copy = new double[array.length]; - System.arraycopy(array,0,copy,0,array.length); - return copy; - } - - /** - * Clones an array of doubles - * @return null if input is null, otherwise return complete copy. - */ - public static final double[][] getCopy(double[][] array) { - - if(array == null) { - return null; - } - double[][] copy = new double[array.length][]; - for(int i = 0 ; i < copy.length ; i++) { - copy[i] = new double[array[i].length]; - System.arraycopy(array[i],0,copy[i],0,array[i].length); - } - return copy; - } - - /** - * Clones an array of ints - * @return null if input is null, otherwise return complete copy. - */ - public static final int[] getCopy(int[] array) { - if(array == null) { - return null; - } - int[] copy = new int[array.length]; - System.arraycopy(array,0,copy,0,array.length); - return copy; - } - - /** Copies all of source into dest - assumes dest to be large enough */ - public static final void copy(double[][] source, double[][] dest) { - for(int i = 0 ; i < source.length ; i++) { - System.arraycopy(source[i],0,dest[i],0,source[i].length); - } - } - - /** - * A simple toString method for an array of doubles. - * No fancy formating. - * Puts spaces between each value - */ - public static final String toString(double[] array) { - StringBuffer sb = new StringBuffer(array.length*7); - for(int i = 0 ; i < array.length ; i++) { - sb.append(array[i]); - sb.append(' '); - } - return sb.toString(); - } - /** - * A simple toString method for an array of ints. - * No fancy formating. - * Puts spaces between each value - */ - public static final String toString(int[] array) { - StringBuffer sb = new StringBuffer(array.length*7); - for(int i = 0 ; i < array.length ; i++) { - sb.append(array[i]); - sb.append(' '); - } - return sb.toString(); - } - - /** - * A simple toString method for an array of doubles. - * No fancy formating. - * Puts spaces between each value - */ - public static final String toString(double[][] array) { - String ss = ""; - for(int i = 0 ; i < array.length ; i++) { - ss+= i+":"+toString(array[i])+'\n'; - } - return ss; - } -} - - - Index: anches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/AttributeNode.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/AttributeNode.java (revision 1578) +++ (revision ) @@ -1,61 +1,0 @@ -// AttributeNode.java -// -// (c) 1999-2001 PAL Development Core Team -// -// This package may be distributed under the -// terms of the Lesser GNU General Public License (LGPL) - - -package de.ugoe.cs.autoquest.tasktrees.alignment.pal.tree; - - -import java.io.*; -import java.util.Enumeration; - - -/** - * interface for a node (includes branch) in a binary/non-binary - * rooted/unrooted tree. Unlike its superclass this node - * can have an arbitrary number of named attributes associated with it. - * - * @version $Id: AttributeNode.java,v 1.4 2001/12/03 11:04:39 korbinian Exp $ - * - * @author Alexei Drummond - * @author Korbinian Strimmer - * - */ - -public interface AttributeNode extends Node { - - /** attribute name for the standard error on a node's height. */ - String NODE_HEIGHT_SE = "node height SE"; - - /** attribute name for the probability of the clade defined by an internal node. */ - String CLADE_PROBABILITY = "clade probability"; - - /** attribute name for the probability of the subtree defined by an internal node. */ - String SUBTREE_PROBABILITY = "subtree probability"; - - /** attribute name for the mean height of this clade in a group of trees. */ - String MEAN_CLADE_HEIGHT = "mean clade height"; - - /** - * Sets a named attribute to the given value. - * @param name the name of the attribute - * @param value the value to set the attribute - */ - void setAttribute(String name, Object value); - - /** - * @return the attribute with the given name or null if it doesn't exist. - * @param name the name of the attribute. - */ - Object getAttribute(String name); - - /** - * @return an enumeration of the attributes that this node has. - */ - Enumeration getAttributeNames(); - -} - Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/FengDoolittleNode.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/FengDoolittleNode.java (revision 1578) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/FengDoolittleNode.java (revision 1579) @@ -14,5 +14,4 @@ import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.NumberSequence; import de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc.Identifier; -import de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc.LabelMapping; @@ -89,59 +88,4 @@ } - public FengDoolittleNode(Node n, boolean keepIds) { - init(n, keepIds); - for (int i = 0; i < n.getChildCount(); i++) { - addChild(new FengDoolittleNode(n.getChild(i), keepIds)); - } - } - - public FengDoolittleNode(Node n, LabelMapping lm) { - init(n, true, lm); - for (int i = 0; i < n.getChildCount(); i++) { - addChild(new FengDoolittleNode(n.getChild(i), lm)); - } - } - - - /** constructor used to clone a node and all children */ - public FengDoolittleNode(Node n) - { - this(n, true); - } - - - - protected void init(Node n) { - init(n, true); - } - /** - * Initialized node instance variables based on given Node. - * children are ignored. - */ - protected void init(Node n, boolean keepId) { - init(n,keepId,null); - } - /** - * Initialized node instance variables based on given Node. - * children are ignored. - * @param lm - may be null - */ - protected void init(Node n, boolean keepId, LabelMapping lm) { - parent = null; - length = n.getBranchLength(); - lengthSE = n.getBranchLengthSE(); - height = n.getNodeHeight(); - if (keepId) { - if(lm!=null) { - identifier = lm.getLabelIdentifier(n.getIdentifier()); - } else { - identifier = n.getIdentifier(); - } - } else { identifier = Identifier.ANONYMOUS; } - - number = n.getNumber(); - sequences = n.getSequences(); - child = null; - } /** Index: anches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/NeighborJoiningTree.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/NeighborJoiningTree.java (revision 1578) +++ (revision ) @@ -1,204 +1,0 @@ -// NeighborJoiningTree.java -// -// (c) 1999-2001 PAL Development Core Team -// -// This package may be distributed under the -// terms of the Lesser GNU General Public License (LGPL) - - -// computational complexity O(numSeqs^3) - - -package de.ugoe.cs.autoquest.tasktrees.alignment.pal.tree; - -import de.ugoe.cs.autoquest.tasktrees.alignment.matrix.UPGMAMatrix; - - -/** - * constructs a neighbor-joining tree from pairwise distances - * - * @version $Id: NeighborJoiningTree.java,v 1.9 2001/07/13 14:39:13 korbinian Exp $ - * - * @author Korbinian Strimmer - * @author Alexei Drummond - */ -public class NeighborJoiningTree extends SimpleTree -{ - // - // Public stuff - // - - /** - * construct NJ tree - * - * @param m distance matrix - */ - public NeighborJoiningTree(UPGMAMatrix m) - { - if (m.size() < 3) - { - new IllegalArgumentException("LESS THAN 3 TAXA IN DISTANCE MATRIX"); - } - - init(m); - - //while (numClusters > 3) - while (true) - { - findNextPair(); - newBranchLengths(); - if (numClusters == 3) - { - break; - } - newCluster(); - } - - finish(); - } - - - // - // Private stuff - // - - private int numClusters; - private Node newCluster; - private int besti, abi; - private int bestj, abj; - private int[] alias; - private double[][] distance; - private double[] r; - private double scale; - - private double getDist(int a, int b) - { - return distance[alias[a]][alias[b]]; - } - - private void init(UPGMAMatrix m) - { - numClusters = m.size(); - - distance = new double[numClusters][numClusters]; - for (int i = 0; i < numClusters; i++) - { - for (int j = 0; j < numClusters; j++) - { - distance[i][j] = m.get(i,j); - } - } - - for (int i = 0; i < numClusters; i++) - { - Node tmp = NodeFactory.createNode(); - //tmp.setIdentifier(m.getIdentifier(i)); - getRoot().addChild(tmp); - } - - alias = new int[numClusters]; - for (int i = 0; i < numClusters; i++) - { - alias[i] = i; - } - - r = new double[numClusters]; - } - - private void finish() - { - if (besti != 0 && bestj != 0) - { - getRoot().getChild(0).setBranchLength(updatedDistance(besti, bestj, 0)); - } - else if (besti != 1 && bestj != 1) - { - getRoot().getChild(1).setBranchLength(updatedDistance(besti, bestj, 1)); - } - else - { - getRoot().getChild(2).setBranchLength(updatedDistance(besti, bestj, 2)); - } - distance = null; - - // make node heights available also - NodeUtils.lengths2Heights(getRoot()); - } - - private void findNextPair() - { - for (int i = 0; i < numClusters; i++) - { - r[i] = 0; - for (int j = 0; j < numClusters; j++) - { - r[i] += getDist(i,j); - } - } - - besti = 0; - bestj = 1; - double smax = -1.0; - scale = 1.0/(numClusters-2); - for (int i = 0; i < numClusters-1; i++) - { - for (int j = i+1; j < numClusters; j++) - { - double sij = (r[i] + r[j] ) * scale - getDist(i, j); - - if (sij > smax) - { - smax = sij; - besti = i; - bestj = j; - } - } - } - abi = alias[besti]; - abj = alias[bestj]; - } - - private void newBranchLengths() - { - double dij = getDist(besti, bestj); - double li = (dij + (r[besti]-r[bestj])*scale)*0.5; - double lj = dij - li; // = (dij + (r[bestj]-r[besti])*scale)*0.5 - - getRoot().getChild(besti).setBranchLength(li); - getRoot().getChild(bestj).setBranchLength(lj); - } - - private void newCluster() - { - // Update distances - for (int k = 0; k < numClusters; k++) - { - if (k != besti && k != bestj) - { - int ak = alias[k]; - distance[ak][abi] = distance[abi][ak] = updatedDistance(besti, bestj, k); - } - } - distance[abi][abi] = 0.0; - - // Replace besti with new cluster - getRoot().joinChildren(besti, bestj); - - // Update alias - for (int i = bestj; i < numClusters-1; i++) - { - alias[i] = alias[i+1]; - } - - numClusters--; - } - - /** - * compute updated distance between the new cluster (i,j) - * to any other cluster k - */ - private double updatedDistance(int i, int j, int k) - { - return (getDist(k, i) + getDist(k, j) - getDist(i, j))*0.5; - } -} Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/NodeFactory.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/NodeFactory.java (revision 1578) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/NodeFactory.java (revision 1579) @@ -31,9 +31,3 @@ return new FengDoolittleNode(); } - - /** constructor used to clone a node and all children */ - public static Node createNode(Node node) - { - return new FengDoolittleNode(node); - } } Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/NodeUtils.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/NodeUtils.java (revision 1578) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/NodeUtils.java (revision 1579) @@ -12,5 +12,4 @@ import de.ugoe.cs.autoquest.tasktrees.alignment.pal.io.FormattedOutput; -import de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc.BranchLimits; import de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc.Identifier; @@ -119,57 +118,5 @@ } - /** - * determines branch lengths of this and all descendent nodes - * from heights - */ - public static void heights2Lengths(Node node) { - heights2Lengths(node, true); //respect minimum - } - - /** - * determines branch lengths of this and all descendent nodes - * from heights - */ - public static void heights2Lengths(Node node, boolean respectMinimum) { - - for (int i = 0; i < node.getChildCount(); i++) { - heights2Lengths(node.getChild(i)); - } - - if (node.isRoot()) { - node.setBranchLength(0.0); - } - else { - node.setBranchLength(node.getParent().getNodeHeight() - node.getNodeHeight()); - if (respectMinimum && (node.getBranchLength() < BranchLimits.MINARC)) - { - node.setBranchLength(BranchLimits.MINARC); - } - } - } - - /** - * determines branch lengths of this node and its immediate descendent nodes - * from heights. - */ - public static void localHeights2Lengths(Node node, boolean respectMinimum) { - - for (int i = 0; i < node.getChildCount(); i++) { - Node child = node.getChild(i); - - child.setBranchLength(node.getNodeHeight() - child.getNodeHeight()); - } - - if (node.isRoot()) { - node.setBranchLength(0.0); - } - else { - node.setBranchLength(node.getParent().getNodeHeight() - node.getNodeHeight()); - if (respectMinimum && (node.getBranchLength() < BranchLimits.MINARC)) - { - node.setBranchLength(BranchLimits.MINARC); - } - } - } + Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/SimpleTree.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/SimpleTree.java (revision 1578) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/SimpleTree.java (revision 1579) @@ -10,10 +10,9 @@ import java.io.PrintWriter; -import java.io.Serializable; import java.io.StringWriter; -import java.util.Hashtable; + import de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc.Identifier; -import de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc.LabelMapping; + @@ -56,9 +55,4 @@ private int numExternalNodes; - /** attributes attached to this tree. */ - private Hashtable[] attributes = null; - - - /** constructor tree consisting solely of root node */ public SimpleTree() { @@ -77,28 +71,4 @@ createNodeList(); } - - /** clone constructor */ - public SimpleTree(Tree tree) - { - root = new FengDoolittleNode(tree.getRoot()); - createNodeList(); - } - - /** clone constructor */ - public SimpleTree(Tree tree, boolean keepIdentifiers) - { - root = new FengDoolittleNode(tree.getRoot(), keepIdentifiers); - createNodeList(); - } - /** - * clone constructor - * @param lm - a label mapping use for translating the original label names into something else - */ - public SimpleTree(Tree tree, LabelMapping lm) - { - root = new FengDoolittleNode(tree.getRoot(), lm); - createNodeList(); - } - @@ -225,29 +195,6 @@ } - private int getIndex(Node node) { - if (node.isLeaf()) return node.getNumber(); - return getExternalNodeCount() + node.getNumber(); - } - - /** - * Sets an named attribute for a given node. - * @param node the node whose attribute is being set. - * @param name the name of the attribute. - * @param value the new value of the attribute. - */ - public void setAttribute(Node node, String name, Object value) { - if (node instanceof AttributeNode) { - ((AttributeNode)node).setAttribute(name, value); - } else { - int index = getIndex(node); - if (attributes == null) { - attributes = new Hashtable[getExternalNodeCount() + getInternalNodeCount()]; - } - if (attributes[index] == null) { - attributes[index] = new Hashtable(); - } - attributes[index].put(name, value); - } - } + + public String toString() { @@ -258,20 +205,4 @@ } - /** - * @return an object representing the named attributed for the numbered node. - * @param node the node being interrogated. - * @param name the name of the attribute of interest. - */ - public Object getAttribute(Node node, String name) { - if (node instanceof AttributeNode) { - return ((AttributeNode)node).getAttribute(name); - } else { - int index = getIndex(node); - if (attributes == null || attributes[index] == null) { - return null; - } - return attributes[index].get(name); - } - } Index: /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/Tree.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/Tree.java (revision 1578) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/Tree.java (revision 1579) @@ -59,17 +59,4 @@ void createNodeList(); - /** - * Sets an named attribute for a given node. - * @param node the node whose attribute is being set. - * @param name the name of the attribute. - * @param value the new value of the attribute. - */ - void setAttribute(Node node, String name, Object value); - /** - * @return an object representing the named attributed for the numbered node. - * @param node the node being interrogated. - * @param name the name of the attribute of interest. - */ - Object getAttribute(Node node, String name); } Index: anches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/TreeParseException.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/TreeParseException.java (revision 1578) +++ (revision ) @@ -1,28 +1,0 @@ -// TreeParseException.java -// -// (c) 1999-2001 PAL Development Core Team -// -// This package may be distributed under the -// terms of the Lesser GNU General Public License (LGPL) - - -package de.ugoe.cs.autoquest.tasktrees.alignment.pal.tree; - - -/** - * exception thrown by ReadTree - * - * @author Korbinian Strimmer - */ -public class TreeParseException extends Exception -{ - - private static final long serialVersionUID = -6890313232581908150L; - - public TreeParseException() {} - - public TreeParseException(String msg) - { - super(msg); - } -} 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 1579) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/UPGMAAligningTree.java (revision 1579) @@ -0,0 +1,215 @@ +// UPGMATree.java +// +// (c) 1999-2001 PAL Development Core Team +// +// This package may be distributed under the +// terms of the Lesser GNU General Public License (LGPL) + +// Known bugs and limitations: +// - computational complexity O(numSeqs^3) +// (this could be brought down to O(numSeqs^2) +// but this needs more clever programming ...) + + +package de.ugoe.cs.autoquest.tasktrees.alignment.pal.tree; + +import java.util.ArrayList; + +import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.NumberSequence; +import de.ugoe.cs.autoquest.tasktrees.alignment.matrix.UPGMAMatrix; +import de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc.Identifier; + + +/** + * constructs a UPGMA tree from pairwise distances + * + * @version $Id: UPGMATree.java,v 1.9 2001/07/13 14:39:13 korbinian Exp $ + * + * @author Korbinian Strimmer + * @author Alexei Drummond + */ +public class UPGMAAligningTree extends SimpleTree +{ + // + // Public stuff + // + + /** + * constructor UPGMA tree + * @param numberseqs + * + * @param m distance matrix + */ + public UPGMAAligningTree(ArrayList numberseqs, UPGMAMatrix m) + { + if (m.size() < 2) + { + new IllegalArgumentException("LESS THAN 2 TAXA IN DISTANCE MATRIX"); + } + + this.numberseqs = numberseqs; + init(m); + + while (true) + { + findNextPair(); + newBranchLengths(); + + if (numClusters == 2) + { + break; + } + + newCluster(); + } + + finish(); + createNodeList(); + } + + + // + // Private stuff + // + private ArrayList numberseqs; + private int numClusters; + private int besti, abi; + private int bestj, abj; + private int[] alias; + private double[][] distance; + + private double[] height; + private int[] oc; + + private double getDist(int a, int b) + { + return distance[alias[a]][alias[b]]; + } + + private void init(UPGMAMatrix m) + { + numClusters = m.size(); + + distance = new double[numClusters][numClusters]; + for (int i = 0; i < numClusters; i++) + { + for (int j = 0; j < numClusters; j++) + { + distance[i][j] = m.get(i,j); + } + } + + for (int i = 0; i < numClusters; i++) + { + Node tmp = NodeFactory.createNode(); + tmp.setIdentifier(new Identifier(Integer.toString(i))); + tmp.addSequence(numberseqs.get(i)); + getRoot().addChild(tmp); + } + + alias = new int[numClusters]; + for (int i = 0; i < numClusters; i++) + { + alias[i] = i; + } + + height = new double[numClusters]; + oc = new int[numClusters]; + for (int i = 0; i < numClusters; i++) + { + height[i] = 0.0; + oc[i] = 1; + } + } + + private void finish() + { + distance = null; + } + + private void findNextPair() + { + besti = 0; + bestj = 1; + double dmin = getDist(0, 1); + for (int i = 0; i < numClusters-1; i++) + { + for (int j = i+1; j < numClusters; j++) + { + if (getDist(i, j) < dmin) + { + dmin = getDist(i, j); + besti = i; + bestj = j; + } + } + } + abi = alias[besti]; + abj = alias[bestj]; + //System.out.println("Found best pair: " + abi + "/" +abj + " - "+ besti+ "/"+bestj +" with distance " + dmin); + + } + + private void newBranchLengths() + { + double dij = getDist(besti, bestj); + + getRoot().getChild(besti).setBranchLength(dij/2.0-height[abi]); + getRoot().getChild(bestj).setBranchLength(dij/2.0-height[abj]); + } + + private void newCluster() + { + // Update distances + for (int k = 0; k < numClusters; k++) + { + if (k != besti && k != bestj) + { + int ak = alias[k]; + double updated = updatedDistance(besti,bestj,k); + distance[ak][abi] = distance[abi][ak] = updated; + } + } + distance[abi][abi] = 0.0; + + // Update UPGMA variables + height[abi] = getDist(besti, bestj)/2.0; + oc[abi] += oc[abj]; + + // Index besti now represent the new cluster + getRoot().joinChildren(besti, bestj); + + // Update alias + for (int i = bestj; i < numClusters-1; i++) + { + alias[i] = alias[i+1]; + } + + numClusters--; + } + + + /** + * compute updated distance between the new cluster (i,j) + * to any other cluster k + */ + private double updatedDistance(int i, int j, int k) + { + int ai = alias[i]; + int aj = alias[j]; + + double ocsum = (double) (oc[ai]+oc[aj]); + double idist = getDist(k,i); + double jdist = getDist(k,j); + //TODO: Dirty hack to deal with infinity, insert proper solution here + if(Double.isInfinite(idist)) { + idist = 100; + } + if(Double.isInfinite(jdist)) { + jdist = 100; + } + + return (oc[ai]/ocsum)*idist+ + (oc[aj]/ocsum)*jdist; + } +} Index: anches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/UPGMATree.java =================================================================== --- /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/UPGMATree.java (revision 1578) +++ (revision ) @@ -1,215 +1,0 @@ -// UPGMATree.java -// -// (c) 1999-2001 PAL Development Core Team -// -// This package may be distributed under the -// terms of the Lesser GNU General Public License (LGPL) - -// Known bugs and limitations: -// - computational complexity O(numSeqs^3) -// (this could be brought down to O(numSeqs^2) -// but this needs more clever programming ...) - - -package de.ugoe.cs.autoquest.tasktrees.alignment.pal.tree; - -import java.util.ArrayList; - -import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.NumberSequence; -import de.ugoe.cs.autoquest.tasktrees.alignment.matrix.UPGMAMatrix; -import de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc.Identifier; - - -/** - * constructs a UPGMA tree from pairwise distances - * - * @version $Id: UPGMATree.java,v 1.9 2001/07/13 14:39:13 korbinian Exp $ - * - * @author Korbinian Strimmer - * @author Alexei Drummond - */ -public class UPGMATree extends SimpleTree -{ - // - // Public stuff - // - - /** - * constructor UPGMA tree - * @param numberseqs - * - * @param m distance matrix - */ - public UPGMATree(ArrayList numberseqs, UPGMAMatrix m) - { - if (m.size() < 2) - { - new IllegalArgumentException("LESS THAN 2 TAXA IN DISTANCE MATRIX"); - } - - this.numberseqs = numberseqs; - init(m); - - while (true) - { - findNextPair(); - newBranchLengths(); - - if (numClusters == 2) - { - break; - } - - newCluster(); - } - - finish(); - createNodeList(); - } - - - // - // Private stuff - // - private ArrayList numberseqs; - private int numClusters; - private int besti, abi; - private int bestj, abj; - private int[] alias; - private double[][] distance; - - private double[] height; - private int[] oc; - - private double getDist(int a, int b) - { - return distance[alias[a]][alias[b]]; - } - - private void init(UPGMAMatrix m) - { - numClusters = m.size(); - - distance = new double[numClusters][numClusters]; - for (int i = 0; i < numClusters; i++) - { - for (int j = 0; j < numClusters; j++) - { - distance[i][j] = m.get(i,j); - } - } - - for (int i = 0; i < numClusters; i++) - { - Node tmp = NodeFactory.createNode(); - tmp.setIdentifier(new Identifier(Integer.toString(i))); - tmp.addSequence(numberseqs.get(i)); - getRoot().addChild(tmp); - } - - alias = new int[numClusters]; - for (int i = 0; i < numClusters; i++) - { - alias[i] = i; - } - - height = new double[numClusters]; - oc = new int[numClusters]; - for (int i = 0; i < numClusters; i++) - { - height[i] = 0.0; - oc[i] = 1; - } - } - - private void finish() - { - distance = null; - } - - private void findNextPair() - { - besti = 0; - bestj = 1; - double dmin = getDist(0, 1); - for (int i = 0; i < numClusters-1; i++) - { - for (int j = i+1; j < numClusters; j++) - { - if (getDist(i, j) < dmin) - { - dmin = getDist(i, j); - besti = i; - bestj = j; - } - } - } - abi = alias[besti]; - abj = alias[bestj]; - //System.out.println("Found best pair: " + abi + "/" +abj + " - "+ besti+ "/"+bestj +" with distance " + dmin); - - } - - private void newBranchLengths() - { - double dij = getDist(besti, bestj); - - getRoot().getChild(besti).setBranchLength(dij/2.0-height[abi]); - getRoot().getChild(bestj).setBranchLength(dij/2.0-height[abj]); - } - - private void newCluster() - { - // Update distances - for (int k = 0; k < numClusters; k++) - { - if (k != besti && k != bestj) - { - int ak = alias[k]; - double updated = updatedDistance(besti,bestj,k); - distance[ak][abi] = distance[abi][ak] = updated; - } - } - distance[abi][abi] = 0.0; - - // Update UPGMA variables - height[abi] = getDist(besti, bestj)/2.0; - oc[abi] += oc[abj]; - - // Index besti now represent the new cluster - getRoot().joinChildren(besti, bestj); - - // Update alias - for (int i = bestj; i < numClusters-1; i++) - { - alias[i] = alias[i+1]; - } - - numClusters--; - } - - - /** - * compute updated distance between the new cluster (i,j) - * to any other cluster k - */ - private double updatedDistance(int i, int j, int k) - { - int ai = alias[i]; - int aj = alias[j]; - - double ocsum = (double) (oc[ai]+oc[aj]); - double idist = getDist(k,i); - double jdist = getDist(k,j); - //TODO: Dirty hack to deal with infinity, insert proper solution here - if(Double.isInfinite(idist)) { - idist = 100; - } - if(Double.isInfinite(jdist)) { - jdist = 100; - } - - return (oc[ai]/ocsum)*idist+ - (oc[aj]/ocsum)*jdist; - } -} 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 1578) +++ /branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRuleAlignment.java (revision 1579) @@ -31,5 +31,5 @@ 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.tree.UPGMATree; +import de.ugoe.cs.autoquest.tasktrees.alignment.pal.tree.UPGMAAligningTree; import de.ugoe.cs.autoquest.tasktrees.taskequality.TaskEquality; import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration; @@ -207,5 +207,5 @@ } //System.out.println(sequenceDistances.toString()); - UPGMATree guidetree = new UPGMATree(numberseqs, sequenceDistances); + UPGMAAligningTree guidetree = new UPGMAAligningTree(numberseqs, sequenceDistances);