X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=src%2Fjalview%2Fanalysis%2FAverageDistanceEngine.java;h=f4d69d5cb4b3e592df21768a2ada643d983ce886;hb=d27e73b6519abfe5922ae716efe9a8dcc58c7751;hp=a3301706a1cf1df72c1d0623035c1a031b9161b8;hpb=8fbc01654883e68f8843ad6632efaabfaf21692e;p=jalview.git

diff --git a/src/jalview/analysis/AverageDistanceEngine.java b/src/jalview/analysis/AverageDistanceEngine.java
index a330170..f4d69d5 100644
--- a/src/jalview/analysis/AverageDistanceEngine.java
+++ b/src/jalview/analysis/AverageDistanceEngine.java
@@ -20,7 +20,9 @@
  */
 package jalview.analysis;
 
+import java.util.ArrayList;
 import java.util.BitSet;
+import java.util.List;
 import java.util.Vector;
 
 import jalview.datamodel.AlignmentAnnotation;
@@ -37,42 +39,110 @@ import jalview.viewmodel.AlignmentViewport;
 public class AverageDistanceEngine extends TreeEngine
 {
   ContactMatrixI cm;
+
   AlignmentViewport av;
+
   AlignmentAnnotation aa;
+
   /**
-   * compute cosine distance matrix for a given contact matrix and create a UPGMA tree
+   * compute cosine distance matrix for a given contact matrix and create a
+   * UPGMA tree
+   * 
    * @param cm
    */
-  public AverageDistanceEngine(AlignmentViewport av, AlignmentAnnotation aa, ContactMatrixI cm)
+  public AverageDistanceEngine(AlignmentViewport av, AlignmentAnnotation aa,
+          ContactMatrixI cm)
   {
-    this.av =av;
+    this.av = av;
     this.aa = aa;
-    this.cm=cm;
+    this.cm = cm;
+    calculate(cm);
+
+  }
+
+  // 0 - normalised dot product
+  // 1 - L1 - ie (abs(v_1-v_2)/dim(v))
+  // L1 is more rational - since can reason about value of difference,
+  // normalised dot product might give cleaner clusters, but more difficult to
+  // understand.
+
+  int mode = 1;
+
+  public void calculate(ContactMatrixI cm)
+  {
+    this.cm = cm;
     node = new Vector<BinaryNode>();
     clusters = new Vector<BitSet>();
     distances = new Matrix(new double[cm.getWidth()][cm.getWidth()]);
-    noseqs=cm.getWidth();
-    done  = new BitSet();
-    for (int i=0;i<cm.getWidth();i++)
+    noseqs = cm.getWidth();
+    done = new BitSet();
+    double moduli[] = new double[cm.getWidth()];
+    double max;
+    if (mode == 0)
+    {
+      max = 1;
+    }
+    else
+    {
+      max = cm.getMax() * cm.getMax();
+    }
+
+    for (int i = 0; i < cm.getWidth(); i++)
     {
       // init the tree engine node for this column
       BinaryNode cnode = new BinaryNode();
       cnode.setElement(Integer.valueOf(i));
-      cnode.setName("c"+i);
+      cnode.setName("c" + i);
       node.addElement(cnode);
       BitSet bs = new BitSet();
       bs.set(i);
       clusters.addElement(bs);
 
       // compute distance matrix element
-      ContactListI ith=cm.getContactList(i);
-      for (int j=0;j<i;j++)
+      ContactListI ith = cm.getContactList(i);
+      distances.setValue(i, i, 0);
+      if (ith==null)
+      {
+        continue;
+      }
+      for (int j = 0; j < i; j++)
       {
         ContactListI jth = cm.getContactList(j);
-        double prd=0;
-        for (int indx=0;indx<cm.getHeight();indx++)
+        if (jth == null)
+        {
+          break;
+        }
+        double prd = 0;
+        for (int indx = 0; indx < cm.getHeight(); indx++)
         {
-          prd+=ith.getContactAt(indx)*jth.getContactAt(indx);
+          if (mode == 0)
+          {
+            if (j == 0)
+            {
+              moduli[i] += ith.getContactAt(indx) * ith.getContactAt(indx);
+            }
+            prd += ith.getContactAt(indx) * jth.getContactAt(indx);
+          }
+          else
+          {
+            prd += Math
+                    .abs(ith.getContactAt(indx) - jth.getContactAt(indx));
+          }
+        }
+        if (mode == 0)
+        {
+          if (j == 0)
+          {
+            moduli[i] = Math.sqrt(moduli[i]);
+          }
+          prd = (moduli[i] != 0 && moduli[j] != 0)
+                  ? prd / (moduli[i] * moduli[j])
+                  : 0;
+          prd = 1 - prd;
+        }
+        else
+        {
+          prd /= cm.getHeight();
         }
         distances.setValue(i, j, prd);
         distances.setValue(j, i, prd);
@@ -81,8 +151,8 @@ public class AverageDistanceEngine extends TreeEngine
 
     noClus = clusters.size();
     cluster();
-    
   }
+
   /**
    * Calculates and saves the distance between the combination of cluster(i) and
    * cluster(j) and all other clusters. An average of the distances from
@@ -177,4 +247,145 @@ public class AverageDistanceEngine extends TreeEngine
     nodej.dist = ((dist / 2) - jh);
   }
 
+  /***
+   * not the right place - OH WELL!
+   */
+
+  /**
+   * Makes a list of groups, where each group is represented by a node whose
+   * height (distance from the root node), as a fraction of the height of the
+   * whole tree, is greater than the given threshold. This corresponds to
+   * selecting the nodes immediately to the right of a vertical line
+   * partitioning the tree (if the tree is drawn with root to the left). Each
+   * such node represents a group that contains all of the sequences linked to
+   * the child leaf nodes.
+   * 
+   * @param threshold
+   * @see #getGroups()
+   */
+  public List<BinaryNode> groupNodes(float threshold)
+  {
+    List<BinaryNode> groups = new ArrayList<BinaryNode>();
+    _groupNodes(groups, getTopNode(), threshold);
+    return groups;
+  }
+
+  protected void _groupNodes(List<BinaryNode> groups, BinaryNode nd,
+          float threshold)
+  {
+    if (nd == null)
+    {
+      return;
+    }
+
+    if ((nd.height / maxheight) > threshold)
+    {
+      groups.add(nd);
+    }
+    else
+    {
+      _groupNodes(groups, nd.left(), threshold);
+      _groupNodes(groups, nd.right(), threshold);
+    }
+  }
+
+  /**
+   * DOCUMENT ME!
+   * 
+   * @param nd
+   *          DOCUMENT ME!
+   * 
+   * @return DOCUMENT ME!
+   */
+  public double findHeight(BinaryNode nd)
+  {
+    if (nd == null)
+    {
+      return maxheight;
+    }
+
+    if ((nd.left() == null) && (nd.right() == null))
+    {
+      nd.height = ((BinaryNode) nd.parent()).height + nd.dist;
+
+      if (nd.height > maxheight)
+      {
+        return nd.height;
+      }
+      else
+      {
+        return maxheight;
+      }
+    }
+    else
+    {
+      if (nd.parent() != null)
+      {
+        nd.height = ((BinaryNode) nd.parent()).height + nd.dist;
+      }
+      else
+      {
+        maxheight = 0;
+        nd.height = (float) 0.0;
+      }
+
+      maxheight = findHeight((BinaryNode) (nd.left()));
+      maxheight = findHeight((BinaryNode) (nd.right()));
+    }
+
+    return maxheight;
+  }
+
+  /**
+   * Search for leaf nodes below (or at) the given node
+   * 
+   * @param top2
+   *          root node to search from
+   * 
+   * @return
+   */
+  public Vector<BinaryNode> findLeaves(BinaryNode top2)
+  {
+    Vector<BinaryNode> leaves = new Vector<BinaryNode>();
+    findLeaves(top2, leaves);
+    return leaves;
+  }
+
+  /**
+   * Search for leaf nodes.
+   * 
+   * @param nd
+   *          root node to search from
+   * @param leaves
+   *          Vector of leaves to add leaf node objects too.
+   * 
+   * @return Vector of leaf nodes on binary tree
+   */
+  Vector<BinaryNode> findLeaves(BinaryNode nd, Vector<BinaryNode> leaves)
+  {
+    if (nd == null)
+    {
+      return leaves;
+    }
+
+    if ((nd.left() == null) && (nd.right() == null)) // Interior node
+    // detection
+    {
+      leaves.addElement(nd);
+
+      return leaves;
+    }
+    else
+    {
+      /*
+       * TODO: Identify internal nodes... if (node.isSequenceLabel()) {
+       * leaves.addElement(node); }
+       */
+      findLeaves(nd.left(), leaves);
+      findLeaves(nd.right(), leaves);
+    }
+
+    return leaves;
+  }
+
 }