X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=src%2Fjalview%2Fanalysis%2FNJTree.java;h=67ce460bb5ba8b158528c421641a603a5495382b;hb=797df64fa2a0a30773d0f48f5494d4155e5a8be3;hp=88bb51c2496f16241ae26f750b7ea43e04577f24;hpb=cc190cfe952a4d8ef8c38247ee35b1a4675da572;p=jalview.git

diff --git a/src/jalview/analysis/NJTree.java b/src/jalview/analysis/NJTree.java
old mode 100755
new mode 100644
index 88bb51c..67ce460
--- a/src/jalview/analysis/NJTree.java
+++ b/src/jalview/analysis/NJTree.java
@@ -1,20 +1,19 @@
 /*
- * Jalview - A Sequence Alignment Editor and Viewer
- * Copyright (C) 2007 AM Waterhouse, J Procter, G Barton, M Clamp, S Searle
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version 2
- * of the License, or (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
+ * Jalview - A Sequence Alignment Editor and Viewer (Version 2.7)
+ * Copyright (C) 2011 J Procter, AM Waterhouse, J Engelhardt, LM Lui, G Barton, M Clamp, S Searle
+ * 
+ * This file is part of Jalview.
+ * 
+ * Jalview is free software: you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License 
+ * as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.
+ * 
+ * Jalview is distributed in the hope that it will be useful, but 
+ * WITHOUT ANY WARRANTY; without even the implied warranty 
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR 
+ * PURPOSE.  See the GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
  */
 package jalview.analysis;
 
@@ -27,40 +26,60 @@ import jalview.util.*;
 
 /**
  * DOCUMENT ME!
- *
+ * 
  * @author $author$
  * @version $Revision$
  */
 public class NJTree
 {
   Vector cluster;
+
   SequenceI[] sequence;
 
-  //SequenceData is a string representation of what the user
-  //sees. The display may contain hidden columns.
+  // SequenceData is a string representation of what the user
+  // sees. The display may contain hidden columns.
   public AlignmentView seqData = null;
 
   int[] done;
+
   int noseqs;
+
   int noClus;
+
   float[][] distance;
+
   int mini;
+
   int minj;
+
   float ri;
+
   float rj;
+
   Vector groups = new Vector();
+
   SequenceNode maxdist;
+
   SequenceNode top;
+
   float maxDistValue;
+
   float maxheight;
+
   int ycount;
+
   Vector node;
+
   String type;
+
   String pwtype;
+
   Object found = null;
+
   Object leaves = null;
 
   boolean hasDistances = true; // normal case for jalview trees
+
   boolean hasBootstrap = false; // normal case for jalview trees
 
   private boolean hasRootDistance = true;
@@ -68,9 +87,13 @@ public class NJTree
   /**
    * Create a new NJTree object with leaves associated with sequences in seqs,
    * and original alignment data represented by Cigar strings.
-   * @param seqs SequenceI[]
-   * @param odata Cigar[]
-   * @param treefile NewickFile
+   * 
+   * @param seqs
+   *          SequenceI[]
+   * @param odata
+   *          Cigar[]
+   * @param treefile
+   *          NewickFile
    */
   public NJTree(SequenceI[] seqs, AlignmentView odata, NewickFile treefile)
   {
@@ -80,20 +103,20 @@ public class NJTree
       seqData = odata;
     }
     /*
-           sequenceString = new String[odata.length];
-           char gapChar = jalview.util.Comparison.GapChars.charAt(0);
-           for (int i = 0; i < odata.length; i++)
-           {
-      SequenceI oseq_aligned = odata[i].getSeq(gapChar);
-        sequenceString[i] = oseq_aligned.getSequence();
-           } */
+     * sequenceString = new String[odata.length]; char gapChar =
+     * jalview.util.Comparison.GapChars.charAt(0); for (int i = 0; i <
+     * odata.length; i++) { SequenceI oseq_aligned = odata[i].getSeq(gapChar);
+     * sequenceString[i] = oseq_aligned.getSequence(); }
+     */
   }
 
   /**
    * Creates a new NJTree object from a tree from an external source
-   *
-   * @param seqs SequenceI which should be associated with leafs of treefile
-   * @param treefile A parsed tree
+   * 
+   * @param seqs
+   *          SequenceI which should be associated with leafs of treefile
+   * @param treefile
+   *          A parsed tree
    */
   public NJTree(SequenceI[] seqs, NewickFile treefile)
   {
@@ -101,17 +124,11 @@ public class NJTree
     top = treefile.getTree();
 
     /**
-     * There is no dependent alignment to be recovered from an
-     * imported tree.
-     *
-             if (sequenceString == null)
-             {
-      sequenceString = new String[seqs.length];
-      for (int i = 0; i < seqs.length; i++)
-      {
-        sequenceString[i] = seqs[i].getSequence();
-      }
-             }
+     * There is no dependent alignment to be recovered from an imported tree.
+     * 
+     * if (sequenceString == null) { sequenceString = new String[seqs.length];
+     * for (int i = 0; i < seqs.length; i++) { sequenceString[i] =
+     * seqs[i].getSequence(); } }
      */
 
     hasDistances = treefile.HasDistances();
@@ -150,8 +167,9 @@ public class NJTree
         if (one2many.contains(nam))
         {
           countOne2Many++;
-          //  if (jalview.bin.Cache.log.isDebugEnabled())
-          //    jalview.bin.Cache.log.debug("One 2 many relationship for "+nam.getName());
+          // if (jalview.bin.Cache.log.isDebugEnabled())
+          // jalview.bin.Cache.log.debug("One 2 many relationship for
+          // "+nam.getName());
         }
         else
         {
@@ -165,26 +183,30 @@ public class NJTree
         j.setPlaceholder(true);
       }
     }
-    //  if (jalview.bin.Cache.log.isDebugEnabled() && countOne2Many>0) {
-    //    jalview.bin.Cache.log.debug("There were "+countOne2Many+" alignment sequence ids (out of "+one2many.size()+" unique ids) linked to two or more leaves.");
-    //  }
-    //  one2many.clear();
+    // if (jalview.bin.Cache.log.isDebugEnabled() && countOne2Many>0) {
+    // jalview.bin.Cache.log.debug("There were "+countOne2Many+" alignment
+    // sequence ids (out of "+one2many.size()+" unique ids) linked to two or
+    // more leaves.");
+    // }
+    // one2many.clear();
   }
 
   /**
    * Creates a new NJTree object.
-   *
-   * @param sequence DOCUMENT ME!
-   * @param type DOCUMENT ME!
-   * @param pwtype DOCUMENT ME!
-   * @param start DOCUMENT ME!
-   * @param end DOCUMENT ME!
+   * 
+   * @param sequence
+   *          DOCUMENT ME!
+   * @param type
+   *          DOCUMENT ME!
+   * @param pwtype
+   *          DOCUMENT ME!
+   * @param start
+   *          DOCUMENT ME!
+   * @param end
+   *          DOCUMENT ME!
    */
-  public NJTree(SequenceI[] sequence,
-                AlignmentView seqData,
-                String type,
-                String pwtype,
-                int start, int end)
+  public NJTree(SequenceI[] sequence, AlignmentView seqData, String type,
+          String pwtype, int start, int end)
   {
     this.sequence = sequence;
     this.node = new Vector();
@@ -205,17 +227,17 @@ public class NJTree
       sdata.addOperation(CigarArray.M, end - start + 1);
       this.seqData = new AlignmentView(sdata, start);
     }
-
-    if (! (type.equals("NJ")))
+    // System.err.println("Made seqData");// dbg
+    if (!(type.equals("NJ")))
     {
       type = "AV";
     }
 
-    if (! (pwtype.equals("PID")))
+    if (!(pwtype.equals("PID")))
     {
       if (ResidueProperties.getScoreMatrix(pwtype) == null)
       {
-        type = "BLOSUM62";
+        pwtype = "BLOSUM62";
       }
     }
 
@@ -223,7 +245,7 @@ public class NJTree
 
     done = new int[sequence.length];
 
-    while ( (i < sequence.length) && (sequence[i] != null))
+    while ((i < sequence.length) && (sequence[i] != null))
     {
       done[i] = 0;
       i++;
@@ -231,33 +253,38 @@ public class NJTree
 
     noseqs = i++;
 
-    distance = findDistances(this.seqData.getSequenceStrings(Comparison.
-        GapChars.charAt(0)));
-
+    distance = findDistances(this.seqData
+            .getSequenceStrings(Comparison.GapChars.charAt(0)));
+    // System.err.println("Made distances");// dbg
     makeLeaves();
+    // System.err.println("Made leaves");// dbg
 
     noClus = cluster.size();
 
     cluster();
+    // System.err.println("Made clusters");// dbg
+
   }
 
   /**
-   * DOCUMENT ME!
-   *
-   * @return DOCUMENT ME!
+   * Generate a string representation of the Tree
+   * 
+   * @return Newick File with all tree data available
    */
   public String toString()
   {
     jalview.io.NewickFile fout = new jalview.io.NewickFile(getTopNode());
 
-    return fout.print(false, true); // distances only
+    return fout.print(isHasBootstrap(),
+    isHasDistances(), isHasRootDistance()); // output all data available for tree
   }
 
   /**
-   *
+   * 
    * used when the alignment associated to a tree has changed.
-   *
-   * @param alignment Vector
+   * 
+   * @param alignment
+   *          Vector
    */
   public void UpdatePlaceHolders(Vector alignment)
   {
@@ -297,8 +324,10 @@ public class NJTree
         {
           if (!leaf.isPlaceholder())
           {
-            // remapping the node to a new sequenceI - should remove any refs to old one.
-            // TODO - make many sequenceI to one leaf mappings possible! (JBPNote)
+            // remapping the node to a new sequenceI - should remove any refs to
+            // old one.
+            // TODO - make many sequenceI to one leaf mappings possible!
+            // (JBPNote)
           }
           leaf.setPlaceholder(false);
           leaf.setElement(nam);
@@ -308,7 +337,8 @@ public class NJTree
           if (!leaf.isPlaceholder())
           {
             // Construct a new placeholder sequence object for this leaf
-            leaf.setElement(new Sequence(leaf.getName(), "THISISAPLACEHLDER"));
+            leaf.setElement(new Sequence(leaf.getName(),
+                    "THISISAPLACEHLDER"));
           }
           leaf.setPlaceholder(true);
 
@@ -316,7 +346,24 @@ public class NJTree
       }
     }
   }
+  /**
+   * rename any nodes according to their associated sequence.
+   * This will modify the tree's metadata! (ie the original NewickFile or newly generated BinaryTree's label data) 
+   */
+  public void renameAssociatedNodes() {
+    applyToNodes(new NodeTransformI() {
 
+      @Override
+      public void transform(BinaryNode node)
+      {
+        Object el = node.element();
+        if (el!=null && el instanceof SequenceI)
+        {
+          node.setName(((SequenceI)el).getName());
+        }
+      }
+    });
+  }
   /**
    * DOCUMENT ME!
    */
@@ -374,29 +421,31 @@ public class NJTree
 
   /**
    * DOCUMENT ME!
-   *
-   * @param i DOCUMENT ME!
-   * @param j DOCUMENT ME!
-   *
+   * 
+   * @param i
+   *          DOCUMENT ME!
+   * @param j
+   *          DOCUMENT ME!
+   * 
    * @return DOCUMENT ME!
    */
   public Cluster joinClusters(int i, int j)
   {
     float dist = distance[i][j];
 
-    int noi = ( (Cluster) cluster.elementAt(i)).value.length;
-    int noj = ( (Cluster) cluster.elementAt(j)).value.length;
+    int noi = ((Cluster) cluster.elementAt(i)).value.length;
+    int noj = ((Cluster) cluster.elementAt(j)).value.length;
 
     int[] value = new int[noi + noj];
 
     for (int ii = 0; ii < noi; ii++)
     {
-      value[ii] = ( (Cluster) cluster.elementAt(i)).value[ii];
+      value[ii] = ((Cluster) cluster.elementAt(i)).value[ii];
     }
 
     for (int ii = noi; ii < (noi + noj); ii++)
     {
-      value[ii] = ( (Cluster) cluster.elementAt(j)).value[ii - noi];
+      value[ii] = ((Cluster) cluster.elementAt(j)).value[ii - noi];
     }
 
     Cluster c = new Cluster(value);
@@ -415,8 +464,8 @@ public class NJTree
 
     SequenceNode sn = new SequenceNode();
 
-    sn.setLeft( (SequenceNode) (node.elementAt(i)));
-    sn.setRight( (SequenceNode) (node.elementAt(j)));
+    sn.setLeft((SequenceNode) (node.elementAt(i)));
+    sn.setRight((SequenceNode) (node.elementAt(j)));
 
     SequenceNode tmpi = (SequenceNode) (node.elementAt(i));
     SequenceNode tmpj = (SequenceNode) (node.elementAt(j));
@@ -440,16 +489,19 @@ public class NJTree
 
   /**
    * DOCUMENT ME!
-   *
-   * @param tmpi DOCUMENT ME!
-   * @param tmpj DOCUMENT ME!
-   * @param dist DOCUMENT ME!
+   * 
+   * @param tmpi
+   *          DOCUMENT ME!
+   * @param tmpj
+   *          DOCUMENT ME!
+   * @param dist
+   *          DOCUMENT ME!
    */
   public void findNewNJDistances(SequenceNode tmpi, SequenceNode tmpj,
-                                 float dist)
+          float dist)
   {
 
-    tmpi.dist = ( (dist + ri) - rj) / 2;
+    tmpi.dist = ((dist + ri) - rj) / 2;
     tmpj.dist = (dist - tmpi.dist);
 
     if (tmpi.dist < 0)
@@ -465,13 +517,16 @@ public class NJTree
 
   /**
    * DOCUMENT ME!
-   *
-   * @param tmpi DOCUMENT ME!
-   * @param tmpj DOCUMENT ME!
-   * @param dist DOCUMENT ME!
+   * 
+   * @param tmpi
+   *          DOCUMENT ME!
+   * @param tmpj
+   *          DOCUMENT ME!
+   * @param dist
+   *          DOCUMENT ME!
    */
   public void findNewDistances(SequenceNode tmpi, SequenceNode tmpj,
-                               float dist)
+          float dist)
   {
     float ih = 0;
     float jh = 0;
@@ -491,30 +546,32 @@ public class NJTree
       snj = (SequenceNode) snj.left();
     }
 
-    tmpi.dist = ( (dist / 2) - ih);
-    tmpj.dist = ( (dist / 2) - jh);
+    tmpi.dist = ((dist / 2) - ih);
+    tmpj.dist = ((dist / 2) - jh);
   }
 
   /**
    * DOCUMENT ME!
-   *
-   * @param i DOCUMENT ME!
-   * @param j DOCUMENT ME!
+   * 
+   * @param i
+   *          DOCUMENT ME!
+   * @param j
+   *          DOCUMENT ME!
    */
   public void findClusterDistance(int i, int j)
   {
-    int noi = ( (Cluster) cluster.elementAt(i)).value.length;
-    int noj = ( (Cluster) cluster.elementAt(j)).value.length;
+    int noi = ((Cluster) cluster.elementAt(i)).value.length;
+    int noj = ((Cluster) cluster.elementAt(j)).value.length;
 
     // New distances from cluster to others
     float[] newdist = new float[noseqs];
 
     for (int l = 0; l < noseqs; l++)
     {
-      if ( (l != i) && (l != j))
+      if ((l != i) && (l != j))
       {
-        newdist[l] = ( (distance[i][l] * noi) + (distance[j][l] * noj)) / (noi +
-            noj);
+        newdist[l] = ((distance[i][l] * noi) + (distance[j][l] * noj))
+                / (noi + noj);
       }
       else
       {
@@ -531,9 +588,11 @@ public class NJTree
 
   /**
    * DOCUMENT ME!
-   *
-   * @param i DOCUMENT ME!
-   * @param j DOCUMENT ME!
+   * 
+   * @param i
+   *          DOCUMENT ME!
+   * @param j
+   *          DOCUMENT ME!
    */
   public void findClusterNJDistance(int i, int j)
   {
@@ -543,10 +602,9 @@ public class NJTree
 
     for (int l = 0; l < noseqs; l++)
     {
-      if ( (l != i) && (l != j))
+      if ((l != i) && (l != j))
       {
-        newdist[l] = ( (distance[i][l] + distance[j][l]) -
-                      distance[i][j]) / 2;
+        newdist[l] = ((distance[i][l] + distance[j][l]) - distance[i][j]) / 2;
       }
       else
       {
@@ -563,10 +621,12 @@ public class NJTree
 
   /**
    * DOCUMENT ME!
-   *
-   * @param i DOCUMENT ME!
-   * @param j DOCUMENT ME!
-   *
+   * 
+   * @param i
+   *          DOCUMENT ME!
+   * @param j
+   *          DOCUMENT ME!
+   * 
    * @return DOCUMENT ME!
    */
   public float findr(int i, int j)
@@ -575,7 +635,7 @@ public class NJTree
 
     for (int k = 0; k < noseqs; k++)
     {
-      if ( (k != i) && (k != j) && (done[k] != 1))
+      if ((k != i) && (k != j) && (done[k] != 1))
       {
         tmp = tmp + distance[i][k];
       }
@@ -591,7 +651,7 @@ public class NJTree
 
   /**
    * DOCUMENT ME!
-   *
+   * 
    * @return DOCUMENT ME!
    */
   public float findMinNJDistance()
@@ -602,7 +662,7 @@ public class NJTree
     {
       for (int j = i + 1; j < noseqs; j++)
       {
-        if ( (done[i] != 1) && (done[j] != 1))
+        if ((done[i] != 1) && (done[j] != 1))
         {
           float tmp = distance[i][j] - (findr(i, j) + findr(j, i));
 
@@ -622,7 +682,7 @@ public class NJTree
 
   /**
    * DOCUMENT ME!
-   *
+   * 
    * @return DOCUMENT ME!
    */
   public float findMinDistance()
@@ -633,7 +693,7 @@ public class NJTree
     {
       for (int j = i + 1; j < noseqs; j++)
       {
-        if ( (done[i] != 1) && (done[j] != 1))
+        if ((done[i] != 1) && (done[j] != 1))
         {
           if (distance[i][j] < min)
           {
@@ -651,7 +711,7 @@ public class NJTree
 
   /**
    * DOCUMENT ME!
-   *
+   * 
    * @return DOCUMENT ME!
    */
   public float[][] findDistances(String[] sequenceString)
@@ -670,8 +730,8 @@ public class NJTree
           }
           else
           {
-            distance[i][j] = 100 -
-                Comparison.PID(sequenceString[i], sequenceString[j]);
+            distance[i][j] = 100 - Comparison.PID(sequenceString[i],
+                    sequenceString[j]);
 
             distance[j][i] = distance[i][j];
           }
@@ -698,10 +758,10 @@ public class NJTree
           {
             try
             {
-              score += pwmatrix.getPairwiseScore(sequenceString[i].charAt(k),
-                                                 sequenceString[j].charAt(k));
-            }
-            catch (Exception ex)
+              score += pwmatrix.getPairwiseScore(
+                      sequenceString[i].charAt(k),
+                      sequenceString[j].charAt(k));
+            } catch (Exception ex)
             {
               System.err.println("err creating BLOSUM62 tree");
               ex.printStackTrace();
@@ -729,37 +789,21 @@ public class NJTree
     }
     return distance;
 
-    //   else
-    /*  else if (pwtype.equals("SW"))
-      {
-          float max = -1;
-
-          for (int i = 0; i < (noseqs - 1); i++)
-          {
-              for (int j = i; j < noseqs; j++)
-              {
-                  AlignSeq as = new AlignSeq(sequence[i], sequence[j], "pep");
-                  as.calcScoreMatrix();
-                  as.traceAlignment();
-                  as.printAlignment(System.out);
-                  distance[i][j] = (float) as.maxscore;
-
-                  if (max < distance[i][j])
-                  {
-                      max = distance[i][j];
-                  }
-              }
-          }
-
-          for (int i = 0; i < (noseqs - 1); i++)
-          {
-              for (int j = i; j < noseqs; j++)
-              {
-                  distance[i][j] = max - distance[i][j];
-                  distance[j][i] = distance[i][j];
-              }
-          }
-      }/*/
+    // else
+    /*
+     * else if (pwtype.equals("SW")) { float max = -1;
+     * 
+     * for (int i = 0; i < (noseqs - 1); i++) { for (int j = i; j < noseqs; j++)
+     * { AlignSeq as = new AlignSeq(sequence[i], sequence[j], "pep");
+     * as.calcScoreMatrix(); as.traceAlignment(); as.printAlignment(System.out);
+     * distance[i][j] = (float) as.maxscore;
+     * 
+     * if (max < distance[i][j]) { max = distance[i][j]; } } }
+     * 
+     * for (int i = 0; i < (noseqs - 1); i++) { for (int j = i; j < noseqs; j++)
+     * { distance[i][j] = max - distance[i][j]; distance[j][i] = distance[i][j];
+     * } } }/
+     */
   }
 
   /**
@@ -787,10 +831,12 @@ public class NJTree
 
   /**
    * Search for leaf nodes.
-   *
-   * @param node root node to search from
-   * @param leaves Vector of leaves to add leaf node objects too.
-   *
+   * 
+   * @param node
+   *          root node to search from
+   * @param leaves
+   *          Vector of leaves to add leaf node objects too.
+   * 
    * @return Vector of leaf nodes on binary tree
    */
   public Vector findLeaves(SequenceNode node, Vector leaves)
@@ -800,7 +846,8 @@ public class NJTree
       return leaves;
     }
 
-    if ( (node.left() == null) && (node.right() == null))
+    if ((node.left() == null) && (node.right() == null)) // Interior node
+    // detection
     {
       leaves.addElement(node);
 
@@ -808,19 +855,25 @@ public class NJTree
     }
     else
     {
-      findLeaves( (SequenceNode) node.left(), leaves);
-      findLeaves( (SequenceNode) node.right(), leaves);
+      /*
+       * TODO: Identify internal nodes... if (node.isSequenceLabel()) {
+       * leaves.addElement(node); }
+       */
+      findLeaves((SequenceNode) node.left(), leaves);
+      findLeaves((SequenceNode) node.right(), leaves);
     }
 
     return leaves;
   }
 
   /**
-   * Find the leaf node with a particular ycount 
-   *
-   * @param node initial point on tree to search from
-   * @param count value to search for
-   *
+   * Find the leaf node with a particular ycount
+   * 
+   * @param node
+   *          initial point on tree to search from
+   * @param count
+   *          value to search for
+   * 
    * @return null or the node with ycound=count
    */
   public Object findLeaf(SequenceNode node, int count)
@@ -830,8 +883,8 @@ public class NJTree
     return found;
   }
 
-  /*#see findLeaf(SequenceNode node, count)
-   *
+  /*
+   * #see findLeaf(SequenceNode node, count)
    */
   public Object _findLeaf(SequenceNode node, int count)
   {
@@ -848,8 +901,8 @@ public class NJTree
     }
     else
     {
-      _findLeaf( (SequenceNode) node.left(), count);
-      _findLeaf( (SequenceNode) node.right(), count);
+      _findLeaf((SequenceNode) node.left(), count);
+      _findLeaf((SequenceNode) node.right(), count);
     }
 
     return found;
@@ -857,8 +910,9 @@ public class NJTree
 
   /**
    * printNode is mainly for debugging purposes.
-   *
-   * @param node SequenceNode
+   * 
+   * @param node
+   *          SequenceNode
    */
   public void printNode(SequenceNode node)
   {
@@ -867,25 +921,26 @@ public class NJTree
       return;
     }
 
-    if ( (node.left() == null) && (node.right() == null))
+    if ((node.left() == null) && (node.right() == null))
     {
-      System.out.println("Leaf = " +
-                         ( (SequenceI) node.element()).getName());
-      System.out.println("Dist " + ( (SequenceNode) node).dist);
+      System.out
+              .println("Leaf = " + ((SequenceI) node.element()).getName());
+      System.out.println("Dist " + ((SequenceNode) node).dist);
       System.out.println("Boot " + node.getBootstrap());
     }
     else
     {
-      System.out.println("Dist " + ( (SequenceNode) node).dist);
-      printNode( (SequenceNode) node.left());
-      printNode( (SequenceNode) node.right());
+      System.out.println("Dist " + ((SequenceNode) node).dist);
+      printNode((SequenceNode) node.left());
+      printNode((SequenceNode) node.right());
     }
   }
 
   /**
    * DOCUMENT ME!
-   *
-   * @param node DOCUMENT ME!
+   * 
+   * @param node
+   *          DOCUMENT ME!
    */
   public void findMaxDist(SequenceNode node)
   {
@@ -894,9 +949,9 @@ public class NJTree
       return;
     }
 
-    if ( (node.left() == null) && (node.right() == null))
+    if ((node.left() == null) && (node.right() == null))
     {
-      float dist = ( (SequenceNode) node).dist;
+      float dist = ((SequenceNode) node).dist;
 
       if (dist > maxDistValue)
       {
@@ -906,14 +961,14 @@ public class NJTree
     }
     else
     {
-      findMaxDist( (SequenceNode) node.left());
-      findMaxDist( (SequenceNode) node.right());
+      findMaxDist((SequenceNode) node.left());
+      findMaxDist((SequenceNode) node.right());
     }
   }
 
   /**
    * DOCUMENT ME!
-   *
+   * 
    * @return DOCUMENT ME!
    */
   public Vector getGroups()
@@ -923,7 +978,7 @@ public class NJTree
 
   /**
    * DOCUMENT ME!
-   *
+   * 
    * @return DOCUMENT ME!
    */
   public float getMaxHeight()
@@ -933,9 +988,11 @@ public class NJTree
 
   /**
    * DOCUMENT ME!
-   *
-   * @param node DOCUMENT ME!
-   * @param threshold DOCUMENT ME!
+   * 
+   * @param node
+   *          DOCUMENT ME!
+   * @param threshold
+   *          DOCUMENT ME!
    */
   public void groupNodes(SequenceNode node, float threshold)
   {
@@ -944,22 +1001,23 @@ public class NJTree
       return;
     }
 
-    if ( (node.height / maxheight) > threshold)
+    if ((node.height / maxheight) > threshold)
     {
       groups.addElement(node);
     }
     else
     {
-      groupNodes( (SequenceNode) node.left(), threshold);
-      groupNodes( (SequenceNode) node.right(), threshold);
+      groupNodes((SequenceNode) node.left(), threshold);
+      groupNodes((SequenceNode) node.right(), threshold);
     }
   }
 
   /**
    * DOCUMENT ME!
-   *
-   * @param node DOCUMENT ME!
-   *
+   * 
+   * @param node
+   *          DOCUMENT ME!
+   * 
    * @return DOCUMENT ME!
    */
   public float findHeight(SequenceNode node)
@@ -969,9 +1027,9 @@ public class NJTree
       return maxheight;
     }
 
-    if ( (node.left() == null) && (node.right() == null))
+    if ((node.left() == null) && (node.right() == null))
     {
-      node.height = ( (SequenceNode) node.parent()).height + node.dist;
+      node.height = ((SequenceNode) node.parent()).height + node.dist;
 
       if (node.height > maxheight)
       {
@@ -986,8 +1044,7 @@ public class NJTree
     {
       if (node.parent() != null)
       {
-        node.height = ( (SequenceNode) node.parent()).height +
-            node.dist;
+        node.height = ((SequenceNode) node.parent()).height + node.dist;
       }
       else
       {
@@ -995,8 +1052,8 @@ public class NJTree
         node.height = (float) 0.0;
       }
 
-      maxheight = findHeight( (SequenceNode) (node.left()));
-      maxheight = findHeight( (SequenceNode) (node.right()));
+      maxheight = findHeight((SequenceNode) (node.left()));
+      maxheight = findHeight((SequenceNode) (node.right()));
     }
 
     return maxheight;
@@ -1004,7 +1061,7 @@ public class NJTree
 
   /**
    * DOCUMENT ME!
-   *
+   * 
    * @return DOCUMENT ME!
    */
   public SequenceNode reRoot()
@@ -1044,7 +1101,7 @@ public class NJTree
   }
 
   /**
-   *
+   * 
    * @return true if original sequence data can be recovered
    */
   public boolean hasOriginalSequenceData()
@@ -1053,9 +1110,9 @@ public class NJTree
   }
 
   /**
-   * Returns original alignment data used for calculation - or null where
-   * not available.
-   *
+   * Returns original alignment data used for calculation - or null where not
+   * available.
+   * 
    * @return null or cut'n'pasteable alignment
    */
   public String printOriginalSequenceData(char gapChar)
@@ -1069,8 +1126,8 @@ public class NJTree
     String[] seqdatas = seqData.getSequenceStrings(gapChar);
     for (int i = 0; i < seqdatas.length; i++)
     {
-      sb.append(new jalview.util.Format("%-" + 15 + "s").form(
-          sequence[i].getName()));
+      sb.append(new jalview.util.Format("%-" + 15 + "s").form(sequence[i]
+              .getName()));
       sb.append(" " + seqdatas[i] + "\n");
     }
     return sb.toString();
@@ -1078,8 +1135,9 @@ public class NJTree
 
   /**
    * DOCUMENT ME!
-   *
-   * @param node DOCUMENT ME!
+   * 
+   * @param node
+   *          DOCUMENT ME!
    */
   public void printN(SequenceNode node)
   {
@@ -1088,67 +1146,81 @@ public class NJTree
       return;
     }
 
-    if ( (node.left() != null) && (node.right() != null))
+    if ((node.left() != null) && (node.right() != null))
     {
-      printN( (SequenceNode) node.left());
-      printN( (SequenceNode) node.right());
+      printN((SequenceNode) node.left());
+      printN((SequenceNode) node.right());
     }
     else
     {
-      System.out.println(" name = " +
-                         ( (SequenceI) node.element()).getName());
+      System.out.println(" name = "
+              + ((SequenceI) node.element()).getName());
     }
 
-    System.out.println(" dist = " + ( (SequenceNode) node).dist + " " +
-                       ( (SequenceNode) node).count + " " +
-                       ( (SequenceNode) node).height);
+    System.out.println(" dist = " + ((SequenceNode) node).dist + " "
+            + ((SequenceNode) node).count + " "
+            + ((SequenceNode) node).height);
   }
 
   /**
    * DOCUMENT ME!
-   *
-   * @param node DOCUMENT ME!
+   * 
+   * @param node
+   *          DOCUMENT ME!
    */
   public void reCount(SequenceNode node)
   {
     ycount = 0;
+    _lycount = 0;
+    // _lylimit = this.node.size();
     _reCount(node);
   }
 
+  private long _lycount = 0, _lylimit = 0;
+
   /**
    * DOCUMENT ME!
-   *
-   * @param node DOCUMENT ME!
+   * 
+   * @param node
+   *          DOCUMENT ME!
    */
   public void _reCount(SequenceNode node)
   {
+    // if (_lycount<_lylimit)
+    // {
+    // System.err.println("Warning: depth of _recount greater than number of nodes.");
+    // }
     if (node == null)
     {
       return;
     }
+    _lycount++;
 
-    if ( (node.left() != null) && (node.right() != null))
+    if ((node.left() != null) && (node.right() != null))
     {
-      _reCount( (SequenceNode) node.left());
-      _reCount( (SequenceNode) node.right());
+
+      _reCount((SequenceNode) node.left());
+      _reCount((SequenceNode) node.right());
 
       SequenceNode l = (SequenceNode) node.left();
       SequenceNode r = (SequenceNode) node.right();
 
-      ( (SequenceNode) node).count = l.count + r.count;
-      ( (SequenceNode) node).ycount = (l.ycount + r.ycount) / 2;
+      ((SequenceNode) node).count = l.count + r.count;
+      ((SequenceNode) node).ycount = (l.ycount + r.ycount) / 2;
     }
     else
     {
-      ( (SequenceNode) node).count = 1;
-      ( (SequenceNode) node).ycount = ycount++;
+      ((SequenceNode) node).count = 1;
+      ((SequenceNode) node).ycount = ycount++;
     }
+    _lycount--;
   }
 
   /**
    * DOCUMENT ME!
-   *
-   * @param node DOCUMENT ME!
+   * 
+   * @param node
+   *          DOCUMENT ME!
    */
   public void swapNodes(SequenceNode node)
   {
@@ -1165,9 +1237,11 @@ public class NJTree
 
   /**
    * DOCUMENT ME!
-   *
-   * @param node DOCUMENT ME!
-   * @param dir DOCUMENT ME!
+   * 
+   * @param node
+   *          DOCUMENT ME!
+   * @param dir
+   *          DOCUMENT ME!
    */
   public void changeDirection(SequenceNode node, SequenceNode dir)
   {
@@ -1178,7 +1252,7 @@ public class NJTree
 
     if (node.parent() != top)
     {
-      changeDirection( (SequenceNode) node.parent(), node);
+      changeDirection((SequenceNode) node.parent(), node);
 
       SequenceNode tmp = (SequenceNode) node.parent();
 
@@ -1226,7 +1300,7 @@ public class NJTree
 
   /**
    * DOCUMENT ME!
-   *
+   * 
    * @return DOCUMENT ME!
    */
   public SequenceNode getMaxDist()
@@ -1236,7 +1310,7 @@ public class NJTree
 
   /**
    * DOCUMENT ME!
-   *
+   * 
    * @return DOCUMENT ME!
    */
   public SequenceNode getTopNode()
@@ -1245,7 +1319,7 @@ public class NJTree
   }
 
   /**
-   *
+   * 
    * @return true if tree has real distances
    */
   public boolean isHasDistances()
@@ -1254,7 +1328,7 @@ public class NJTree
   }
 
   /**
-   *
+   * 
    * @return true if tree has real bootstrap values
    */
   public boolean isHasBootstrap()
@@ -1267,11 +1341,22 @@ public class NJTree
     return hasRootDistance;
   }
 
+  /**
+   * apply the given transform to all the nodes in the tree.
+   * 
+   * @param nodeTransformI
+   */
+  public void applyToNodes(NodeTransformI nodeTransformI)
+  {
+    for (Enumeration nodes = node.elements(); nodes.hasMoreElements(); nodeTransformI
+            .transform((BinaryNode) nodes.nextElement()))
+      ;
+  }
 }
 
 /**
  * DOCUMENT ME!
- *
+ * 
  * @author $author$
  * @version $Revision$
  */
@@ -1281,8 +1366,9 @@ class Cluster
 
   /**
    * Creates a new Cluster object.
-   *
-   * @param value DOCUMENT ME!
+   * 
+   * @param value
+   *          DOCUMENT ME!
    */
   public Cluster(int[] value)
   {