src/jalview/analysis/TreeEngine.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
   3  * Copyright (C) $$Year-Rel$$ The Jalview Authors
   4  *
   5  * This file is part of Jalview.
   6  *
   7  * Jalview is free software: you can redistribute it and/or
   8  * modify it under the terms of the GNU General Public License
   9  * as published by the Free Software Foundation, either version 3
  10  * of the License, or (at your option) any later version.
  11  *
  12  * Jalview is distributed in the hope that it will be useful, but
  13  * WITHOUT ANY WARRANTY; without even the implied warranty
  14  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE.  See the GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
  19  * The Jalview Authors are detailed in the 'AUTHORS' file.
  20  */
  21 package jalview.analysis;
  22
  23 import java.util.BitSet;
  24 import java.util.Vector;
  25
  26 import jalview.datamodel.BinaryNode;
  27 import jalview.datamodel.SequenceNode;
  28 import jalview.math.MatrixI;
  29
  30 public abstract class TreeEngine
  31 {
  32
  33   protected Vector<BitSet> clusters;
  34
  35   protected BitSet done;
  36
  37   protected int noseqs;
  38
  39   protected int noClus;
  40
  41   protected MatrixI distances;
  42
  43   protected double ri;
  44
  45   protected double rj;
  46
  47   protected Vector<BinaryNode> node;
  48
  49   BinaryNode maxdist;
  50
  51   double maxDistValue;
  52
  53   protected int mini;
  54
  55   protected int minj;
  56
  57   protected BinaryNode top;
  58
  59   protected int ycount;
  60
  61   double maxheight;
  62
  63   /**
  64    * Calculates and returns r, whatever that is
  65    *
  66    * @param i
  67    * @param j
  68    *
  69    * @return
  70    */
  71   protected double findr(int i, int j)
  72   {
  73     double tmp = 1;
  74
  75     for (int k = 0; k < noseqs; k++)
  76     {
  77       if ((k != i) && (k != j) && (!done.get(k)))
  78       {
  79         tmp = tmp + distances.getValue(i, k);
  80       }
  81     }
  82
  83     if (noClus > 2)
  84     {
  85       tmp = tmp / (noClus - 2);
  86     }
  87
  88     return tmp;
  89   }
  90
  91   /**
  92    * Merges cluster(j) to cluster(i) and recalculates cluster and node distances
  93    *
  94    * @param i
  95    * @param j
  96    */
  97   protected void joinClusters(final int i, final int j)
  98   {
  99     double dist = distances.getValue(i, j);
 100
 101     ri = findr(i, j);
 102     rj = findr(j, i);
 103
 104     findClusterDistance(i, j);
 105
 106     BinaryNode sn = new BinaryNode();
 107
 108     sn.setLeft((node.elementAt(i)));
 109     sn.setRight((node.elementAt(j)));
 110
 111     BinaryNode tmpi = (node.elementAt(i));
 112     BinaryNode tmpj = (node.elementAt(j));
 113
 114     findNewDistances(tmpi, tmpj, dist);
 115
 116     tmpi.setParent(sn);
 117     tmpj.setParent(sn);
 118
 119     node.setElementAt(sn, i);
 120
 121     /*
 122      * move the members of cluster(j) to cluster(i)
 123      * and mark cluster j as out of the game
 124      */
 125     clusters.get(i).or(clusters.get(j));
 126     clusters.get(j).clear();
 127     done.set(j);
 128   }
 129
 130   protected abstract void findNewDistances(BinaryNode nodei,
 131           BinaryNode nodej, double previousDistance);
 132
 133   /**
 134    * Calculates and saves the distance between the combination of cluster(i) and
 135    * cluster(j) and all other clusters. The form of the calculation depends on
 136    * the tree clustering method being used.
 137    *
 138    * @param i
 139    * @param j
 140    */
 141   protected abstract void findClusterDistance(int i, int j);
 142
 143   /**
 144    * Finds the node, at or below the given node, with the maximum distance, and
 145    * saves the node and the distance value
 146    *
 147    * @param nd
 148    */
 149   protected void findMaxDist(BinaryNode nd)
 150   {
 151     if (nd == null)
 152     {
 153       return;
 154     }
 155
 156     if ((nd.left() == null) && (nd.right() == null))
 157     {
 158       double dist = nd.dist;
 159
 160       if (dist > maxDistValue)
 161       {
 162         maxdist = nd;
 163         maxDistValue = dist;
 164       }
 165     }
 166     else
 167     {
 168       findMaxDist((BinaryNode) nd.left());
 169       findMaxDist((BinaryNode) nd.right());
 170     }
 171   }
 172
 173   /**
 174    * Form clusters by grouping sub-clusters, starting from one sequence per
 175    * cluster, and finishing when only two clusters remain
 176    */
 177   protected void cluster()
 178   {
 179     while (noClus > 2)
 180     {
 181       findMinDistance();
 182
 183       joinClusters(mini, minj);
 184
 185       noClus--;
 186     }
 187
 188     int rightChild = done.nextClearBit(0);
 189     int leftChild = done.nextClearBit(rightChild + 1);
 190
 191     joinClusters(leftChild, rightChild);
 192     top = (node.elementAt(leftChild));
 193
 194     reCount(top);
 195     findHeight(top);
 196     findMaxDist(top);
 197   }
 198
 199   /**
 200    * Returns the minimum distance between two clusters, and also sets the
 201    * indices of the clusters in fields mini and minj
 202    *
 203    * @return
 204    */
 205   protected abstract double findMinDistance();
 206
 207   /**
 208    * DOCUMENT ME!
 209    *
 210    * @param nd
 211    *          DOCUMENT ME!
 212    */
 213   protected void _reCount(BinaryNode nd)
 214   {
 215     // if (_lycount<_lylimit)
 216     // {
 217     // jalview.bin.Console.errPrintln("Warning: depth of _recount greater than number of
 218     // nodes.");
 219     // }
 220     if (nd == null)
 221     {
 222       return;
 223     }
 224     // _lycount++;
 225
 226     if ((nd.left() != null) && (nd.right() != null))
 227     {
 228
 229       _reCount(nd.left());
 230       _reCount((BinaryNode) nd.right());
 231
 232       BinaryNode l = nd.left();
 233       BinaryNode r = nd.right();
 234
 235       nd.count = l.count + r.count;
 236       nd.ycount = (l.ycount + r.ycount) / 2;
 237     }
 238     else
 239     {
 240       nd.count = 1;
 241       nd.ycount = ycount++;
 242     }
 243     // _lycount--;
 244   }
 245
 246   /**
 247    * DOCUMENT ME!
 248    *
 249    * @param nd
 250    *          DOCUMENT ME!
 251    *
 252    * @return DOCUMENT ME!
 253    */
 254   double findHeight(BinaryNode nd)
 255   {
 256     if (nd == null)
 257     {
 258       return maxheight;
 259     }
 260
 261     if ((nd.left() == null) && (nd.right() == null))
 262     {
 263       nd.height = ((BinaryNode) nd.parent()).height + nd.dist;
 264
 265       if (nd.height > maxheight)
 266       {
 267         return nd.height;
 268       }
 269       else
 270       {
 271         return maxheight;
 272       }
 273     }
 274     else
 275     {
 276       if (nd.parent() != null)
 277       {
 278         nd.height = ((BinaryNode) nd.parent()).height + nd.dist;
 279       }
 280       else
 281       {
 282         maxheight = 0;
 283         nd.height = (float) 0.0;
 284       }
 285
 286       maxheight = findHeight((BinaryNode) (nd.left()));
 287       maxheight = findHeight((BinaryNode) (nd.right()));
 288     }
 289
 290     return maxheight;
 291   }
 292
 293   /**
 294    * DOCUMENT ME!
 295    *
 296    * @param nd
 297    *          DOCUMENT ME!
 298    */
 299   void reCount(BinaryNode nd)
 300   {
 301     ycount = 0;
 302     // _lycount = 0;
 303     // _lylimit = this.node.size();
 304     _reCount(nd);
 305   }
 306
 307   /**
 308    * DOCUMENT ME!
 309    *
 310    * @return DOCUMENT ME!
 311    */
 312   public BinaryNode getTopNode()
 313   {
 314     return top;
 315   }
 316
 317 }